Chapter 11 Dynamic Programming - Unicamp

1 53311 Dynamic ProgrammingDynamic Programming is a useful mathematical technique for making a sequence of in-terrelated decisions. It provides a systematic procedure for determining the optimal com-bination of contrast to linear Programming , there does not exist a standard mathematical for-mulation of the Dynamic Programming problem. Rather, Dynamic Programming is a gen-eral type of approach to problem solving, and the particular equations used must be de-veloped to fit each situation. Therefore, a certain degree of ingenuity and insight into thegeneral structure of Dynamic Programming problems is required to recognize when andhow a problem can be solved by Dynamic Programming procedures.

2 These abilities canbest be developed by an exposure to a wide variety of Dynamic Programming applicationsand a study of the characteristics that are common to all these situations. A large numberof illustrative examples are presented for this A PROTOTYPE EXAMPLE FOR Dynamic PROGRAMMINGEXAMPLE 1 The Stagecoach ProblemThe STAGECOACH PROBLEM is a problem specially constructed1to illustrate the fea-tures and to introduce the terminology of Dynamic Programming . It concerns a mythicalfortune seeker in Missouri who decided to go west to join the gold rush in California dur-ing the mid-19th century. The journey would require traveling by stagecoach through un-settled country where there was serious danger of attack by marauders.

3 Although his start-ing point and destination were fixed, he had considerable choice as to which states (orterritories that subsequently became states) to travel through en route. The possible routesare shown in Fig. , where each state is represented by a circled letter and the direc-tion of travel is always from left to right in the diagram. Thus, four stages (stagecoachruns) were required to travel from his point of embarkation in state A(Missouri) to hisdestination in state J(California).This fortune seeker was a prudent man who was quite concerned about his safety.

4 Af-ter some thought, he came up with a rather clever way of determining the safest route. Life1 This problem was developed by Professor Harvey M. Wagner while he was at Stanford policies were offered to stagecoach passengers. Because the cost of the policyfor taking any given stagecoach run was based on a careful evaluation of the safety of thatrun, the safest route should be the one with the cheapest total life insurance cost for the standard policy on the stagecoach run from state ito state j,whichwill be denoted by cij,is53411 Dynamic PROGRAMMING34746324415146333243 BCDEFGHIJABCDEFGHIT hese costs are also shown in Fig.

5 Shall now focus on the question of which route minimizes the total cost of the ProblemFirst note that the shortsighted approach of selecting the cheapest run offered by each suc-cessive stage need not yield an overall optimal decision. Following this strategy wouldgive the route A B F I J, at a total cost of 13. However, sacrificing a little onone stage may permit greater savings thereafter. For example,A D Fis cheaperoverall than A B possible approach to solving this problem is to use trial and , thenumber of possible routes is large (18), and having to calculate the total cost for eachroute is not an appealing road system and costsfor the stagecoach problem also can be formulated as a shortest-path problem(see Sec.)

6 , where costshere play the roleof distancesin the shortest-path problem. The algorithm presented in Sec. actually uses the philosophy ofdynamic Programming . However, because the present problem has a fixed number of stages, the Dynamic pro-gramming approach presented here is even , Dynamic Programming provides a solution with much less effort than ex-haustive enumeration. (The computational savings are enormous for larger versions of thisproblem.) Dynamic Programming starts with a small portion of the original problem andfinds the optimal solution for this smaller problem. It then gradually enlarges the prob-lem, finding the current optimal solution from the preceding one, until the original prob-lem is solved in its the stagecoach problem, we start with the smaller problem where the fortuneseeker has nearly completed his journey and has only one more stage (stagecoach run) togo.

7 The obvious optimal solution for this smaller problem is to go from his current state(whatever it is) to his ultimate destination (state J). At each subsequent iteration, the prob-lem is enlarged by increasing by 1 the number of stages left to go to complete the jour-ney. For this enlarged problem, the optimal solution for where to go next from each pos-sible state can be found relatively easily from the results obtained at the preceding details involved in implementing this approach the decision variables xn(n 1, 2, 3, 4) be the immediate destina-tion on stage n(the nth stagecoach run to be taken).

8 Thus, the route selected is A x1 x2 x3 x4, where x4 fn(s,xn) be the total cost of the best overall policyfor the remainingstages, giventhat the fortune seeker is in state s, ready to start stage n, and selects xnas the immedi-ate destination. Given sand n, let xn* denote any value of xn(not necessarily unique) thatminimizes fn(s,xn), and let fn*(s) be the corresponding minimum value of fn(s,xn). Thus,fn*(s) min fn(s,xn) fn(s,xn*),xnwherefn(s,xn) immediate cost (stage n) minimum future cost (stages n 1 onward) csxn fn* 1(xn).The value of csxnis given by the preceding tables for cijby setting i s(the current state)and j xn(the immediate destination).

9 Because the ultimate destination (state J) is reachedat the end of stage 4,f5*(J) objective is to find f1*(A) and the corresponding route. Dynamic programmingfinds it by successively finding f4*(s),f3*(s),f2*(s), for each of the possible states sandthen using f2*(s) to solve for f1*(A).1 Solution the fortune seeker has only one more stage to go (n 4),his route thereafter is determined entirely by his current state s(either Hor I) and his fi-nal destination x4 J, so the route for this final stagecoach run is s J. Therefore, sincef4*(s) f4(s,J) cs,J, the immediate solution to the n 4 problem A PROTOTYPE EXAMPLE FOR Dynamic PROGRAMMING535n 4:sf4*(s)x4*H3JI4J1 Because this procedure involves moving backwardstage by stage, some writers also count nbackward to denotethe number of remaining stagesto the destination.

10 We use the more natural forward countingfor greater the fortune seeker has two more stages to go (n 3), the solution procedurerequires a few calculations. For example, suppose that the fortune seeker is in state , as depicted below, he must next go to either state Hor Iat an immediate cost ofcF,H 6 or cF,I 3, respectively. If he chooses state H, the minimum additional cost af-ter he reaches there is given in the preceding table as f4*(H) 3, as shown above the Hnode in the diagram. Therefore, the total cost for this decision is 6 3 9. If he choosesstate Iinstead, the total cost is 3 4 7, which is smaller.