《deterministic dynamic programming》由会员分享，可在线阅读，更多相关《deterministic dynamic programming（56页珍藏版）》请在金锄头文库上搜索。
1、?Match PuzzleE X A M P L E 1MilkE X A M P L E 2This section covers topics that may be omitted with no loss of continuity.Deterministic Dynamic ProgrammingDynamic programming is a technique that can be used to solve many optimization problems. In most applications, dynamic programming obtains solutio
2、ns by working backward from the end of a problem toward the beginning, thus breaking up a large, unwieldy problem into a series of smaller, more tractable problems. We introduce the idea of working backward by solving two well-known puzzles and then show how dynamic programming can be used to solve
3、network, inventory, and resource- allocation problems. We close the chapter by showing how to use spreadsheets to solve dynamic programming problems.18.1Two PuzzlesIn this section, we show how working backward can make a seemingly difficult problem almost trivial to solve.Suppose there are 30 matche
4、s on a table. I begin by picking up 1, 2, or 3 matches. Then my opponent must pick up 1, 2, or 3 matches. We continue in this fashion until the last match is picked up. The player who picks up the last match is the loser. How can I (thefirst player) be sure of winning the game?SolutionIf I can ensur
5、e that it will be my opponents turn when 1 match remains, I will certainly win. Working backward one step, if I can ensure that it will be my opponents turn when 5 matches remain, I will win. The reason for this is that no matter what he does when 5 matches re- main, I can make sure that when he has
6、 his next turn, only 1 match will remain. For exam- ple, suppose it is my opponents turn when 5 matches remain. If my opponent picks up 2 matches, I will pick up 2 matches, leaving him with 1 match and sure defeat. Similarly, if I can force my opponent to play when 5, 9, 13, 17, 21, 25, or 29 matche
7、s remain, I am sureof victory. Thus, I cannot lose if I pick up 30 ? 29 ? 1 match on my first turn. Then I sim- ply make sure that my opponent will always be left with 29, 25, 21, 17, 13, 9, or 5 matches on his turn. Notice that we have solved this puzzle by working backward from the end of the prob
8、lem toward the beginning. Try solving this problem without working backward!I have a 9-oz cup and a 4-oz cup. My mother has ordered me to bring home exactly 6 oz of milk. How can I accomplish this goal?962C H A P T E R1 8Deterministic Dynamic ProgrammingSolutionBy starting near the end of the proble
9、m, I cleverly realize that the problem can easily besolved if I can somehow get 1 oz of milk into the 4-oz cup. Then I can fill the 9-oz cupand empty 3 oz from the 9-oz cup into the partially filled 4-oz cup. At this point, I willbe left with 6 oz of milk. After I have this flash of insight, the sol
10、ution to the problemmay easily be described as in Table 1 (the initial situation is written last, and the final sit-uation is written first).P R O B L E M SGroup A1Suppose there are 40 matches on a table. I begin by picking up 1, 2, 3, or 4 matches. Then my opponent must pick up 1, 2, 3, or 4 matche
11、s. We continue until the last match is picked up. The player who picks up the last match is the loser. Can I be sure of victory? If so, how?2Three players have played three rounds of a gambling game. Each round has one loser and two winners. The losing player must pay each winner the amount of money
12、 that the winning player had at the beginning of the round. At the end of the three rounds each player has $10. You are told that each player has won one round. By working backward, determine the original stakes of the three players. Note: If the answer turns out to be (for example) 5, 15, 10, dont
13、worry about which player had which stake; we cant really tell which player ends up with how much, but we can determine the numerical values of the original stakes.Group B3We have 21 coins and are told that one is heavier than any of the other coins. How many weighings on a balancewill it take to fin
14、d the heaviest coin? (Hint: If the heaviestcoin is in a group of three coins, we can find it in one weighing. Then work backward to two weighings, and so on.)4Given a 7-oz cup and a 3-oz cup, explain how we can return from a well with 5 oz of water.18.2A Network ProblemMany applications of dynamic p
15、rogramming reduce to finding the shortest (or longest) path that joins two points in a given network. The following example illustrates how dynamicprogramming (working backward) can be used to find the shortest path in a network.TA B L E 1 Moves in the Cup-and-Milk ProblemNo. of OuncesNo. of Ounces
16、in 9-oz Cupin 4-oz Cup60 64 91 01 10 14 50 54 90 001 8 . 2A Network Problem963Joe Cougar lives in New York City, but he plans to drive to Los Angeles to seek fame and fortune. Joes funds are limited, so he has decided to spend each night on his trip at a friends house. Joe has friends in Columbus, Nashville, Louisville, Kansas City, Omaha, Dallas, San Antonio, and Denver. Joe knows that after one days drive he can reach Columbus, Nashville, or Louisville. After two da
