Dynamic Programming Examples - cvut.cz

1 Dynamic ProgrammingExamples1. Minimum cost from Sydney to Perth2. Economic Feasibility Study3. 0/1 Knapsack problem4. Sequence Alignment problemMinimum Cost from Sydney to PerthBased on M. A. Rosenman: Tutorial - Dynamic Programming ~mike/ Problem definition Travelling from home in Sydney to a hotel in Perth. Three stopovers on the way a number of choices of towns for each stop, a number of hotels to choose from in each city. Each trip has a different distance resulting in a different cost (petrol). Hotels have different costs. The goal is to select a route to and a hotel in Perth so that the overall cost of the trip is Cost from Sydney to Perth Diagrammatic representation of the problemStage: 0 (Sydney) 1234 (Perth)707050607070507050808060 Petrol costHotel costMinimum Cost from Sydney to Perth Recursive definition of solution in terms of sub-problem solutionsOptimal function.

2 With base casewhere nis the stage (stopover) number,iis a city on stopover n,jis a city from which we can arrive at i,kis a hotel in city i()()()(),,min__,,1j kV i nhotel cost kpetrol cost j iV j n=++ (), 00V i=Minimum Cost from Sydney to PerthS9212 + 80CS888 + 80BS9222 + 70 AfromcoststartStage 1 Minimum Cost from Sydney to PerthStage 2B16892+13+70=17588+10+70=16892+10+70=17 2EA15092+13+50=15588+25+50=16392+8+50=15 0 DfromcostCBAM inimum Cost from Sydney to PerthStage 3D225168+12+50=230150+25+50=225FE248168+ 10+70=248150+30+70=250GE235168+7+60=2351 50+27+60=237ID238168+8=70=246150+18+70=2 38 HfromcostEDMinimum Cost from Sydney to PerthStage

3 4238+10+60=308238+10+70=318238+20+50=308 HI300235+15+50=300248+8+50=306225+28+50= 303JF300235+7+60=302248+10+60=318225+15+ 60=300LF308235+10+70=315248+10+70=328225 +13+70=308 KfromcostIGFM inimum Cost from Sydney to PerthStage 4238+10+60=308238+10+70=318238+20+50=308 HI300235+15+50=300248+8+50=306225+28+50= 303JF300235+7+60=302248+10+60=318225+15+ 60=300LF308235+10+70=315248+10+70=328225 +13+70=308 KfromcostIGF Generating solution routes by tracking backwards through the tablesSolution_1 = {I, J} Minimum Cost from Sydney to PerthStage 3 Generating solution routes by tracking backwards through the tablesSolution_1 = {E, I, J}D225168+12+50=230150+25+50=225FE248168 +10+70=248150+30+70=250GE235168+7+60=235 150+27+60=237ID238168+8=70=246150+18+70= 238 HfromcostEDMinimum Cost from Sydney to PerthStage 2 Generating solution routes by tracking backwards through the tablesSolution_1 = {B, E, I, J} Question:What is the second optimal solution?

4 B16892+13+70=17588+10+70=16892+10+70=172 EA15092+13+50=15588+25+50=16392+8+50=150 DfromcostCBAE conomic Feasibility StudyBased on M. A. Rosenman: Tutorial - Dynamic Programming ~mike/ Problem definition We are asked for an advice how to best utilize a large urban area in an expanding town. Envisaged is a mixed project of housing, retail, office and hotel areas. Rental income is a function of the floor areas allocated to each activity. The total floor area is limited to 7 units. The goal is to find the mix of development which will maximize the Feasibility StudyExpected annual profit for areas of 0-7 units allocated to each development type in $1000 Economic Feasibility StudyDiagrammatic representationEconomic Feasibility Study Recursive definition of solution in terms of sub-problem solutionsOptimal function.

5 With base case where nis the stage number corresponding to the development is the total amount of area units allocated in stage n,ais the amount of area units allocated to development type n,Ris the return generated by aunits of development type n.()()()0,max,1,aAV n AR n aV nA a==+ ..(), 00V n=Economic Feasibility StudyRiis the return generated by the total number of area units allocated in i-th the number of area units allocated in (i-1)-th Feasibility Study211 Economic Feasibility Study Question:Can you generate the optimal solution by tracking backwards through the tables?

6 Economic Feasibility Study Solution:Housing=2, Retail=2, Office=0, Hotel=3 Maximal return = 331/0 Knapsack problemBased on Dr. Shieu-Hong Lin lecture notes: Problem definition Input: a set of S={s1,.., sn} of n items where each sihas its value viand weight wi, and a knapsack capacity W. The goal is to choose a subset O of S such that the total weight of the items chosen does not exceed W and the sum of items viin O is maximal with respect to any other subset that meets the constraint. Note that each item sieither is or is not chosen to :What would be a successful strategy for finding the optimal solution if we were allowed to add a fraction xiof each item to the knapsack?

7 1/0 Knapsack problem Decompose the problem into smaller us assume the sequence of items S={s1, s2, s3, .., sn}.Suppose the optimal solution for S and W is a subset O={s2, s4, sk}, in which skis the highest numbered item in the sequence of items:S={s1, s2, s3, s4, .., sk-1, sk, ..,sn}Then, O-{sk} is an optimal solution for the sub-problem Sk-1={s1, .., sk-1} and capacity value of the complete problem S would simply be the value calculated for this sub-problem Sk-1plus the value Knapsack problem Recursive definition of solution in terms of sub-problem construct a matrix V[ , ].For 0 i n, and 0 w W, the entry V[i, w] will store the maximum (combined) value of any subset of items {1, 2.}

8 , i} of (combined) weight at most value V(i,w) represents the optimal solution to this sub-problem: What would the value be if our knapsack weight was just w and we were only choosing among the first k items?If we can compute all the entries of this array, then the array entry V(n, W) will contain the maximal weight (at most W) of items selected from the whole set S, that is, the solution to our Knapsack problem Recursive definition of solution in terms of sub-problem solutionsOptimal function:with base cases ()()(),max, 1 for 1, ,01,iiV i wV iiwvwnwwV iW= + ()0,0Vw=( , ) 0 for 0V i ww=<leave item itake item i1/0 Knapsack problem Bottom-up computation: Compute the table usingrow by row.

9 ()()(),max,, fo1r 1,1 ,,0iiv V iw wVV i wiw Wiwn= + (0, ) 0 for all 0, Vww W= ( , 0) 0 for 1V ii n= 1/0 Knapsack problem Example: Let W=10 and The final output is V(4, 10)= :How do we find the optimal subset of items?1/0 Knapsack problem Recovering the items that produce the optimal value: Start at V[n, W] and track backwards through the : If V(i, w)=V(i-1, w)then item skwas not added to the the trace at V[i-1, w]. If V(i, w)>V(i-1, w)then item skwas added to the the trace one row higher at V(i-1, w-wi). The optimal subset is O={2, 4} in this case.

10 ()()()1,0,max,,11,i nw WiiV iwV i wv V iw w + = Sequence Alignment Based on Advanced Dynamic Programming Tutorial by Eric C. Problem definition Given two sequences X and Y of length m and n, respectively, composed of characters from alphabet A. The goal is to find the best alignment between the two sequencesconsidering the following scoring scheme: Si,j=2 if the residue at position i of sequence X is the same as theresidue at position j of sequence Y (match score), Si,j=-1 if the residue at position i of sequence X is not the same as the residue at position j of sequence Y (mismatch score), w=-2 if either the residue at position i of sequence X or the residue at position j of sequence Y is a space - (gap penalty).