Dynamic ProgrammingSlide 2General characteristics of Dynamic ProgrammingDivision into stagesStatesDecisionsOptimal Policy and Principle of OptimalityA typical example: Shortest PathShortest Path: network figureShortest Path problem: SolutionSlide 11Stage 3 computationsSlide 13Stage 2 computationsSlide 15Stage 1 computationsSlide 17Recursive solution to the problemDynamic Programming•Deterministic Dynamic Programming• A shortest path exampleDynamic Programming•Dynamic programming is a widely-used mathematical technique for solving problems that can be divided into stages and where decisions are required in each stage. •The goal of dynamic programming is to find a combination of decisions that optimizes a certain amount associated with a system.General characteristics of Dynamic Programming•The problem structure is divided into stages•Each stage has a number of states associated with it•Making decisions at one stage transforms one state of the current stage into a state in the next stage. •Given the current state, the optimal decision for each of the remaining states does not depend on the previous states or decisions. This is known as the principle of optimality for dynamic programming. •The principle of optimality allows to solve the problem stage by stage recursively.Division into stagesThe problem is divided into smaller subproblems each of them represented by a stage. The stages are defined in many different ways depending on the context of the problem. If the problem is about long-time development of a system then the stages naturally correspond to time periods. If the goal of the problem is to move some objects from one location to another on a map then partitioning the map into several geographical regions might be the natural division into stages. Generally, if an accomplishment of a certain task can be considered as a multi-step process then each stage can be defined as a step in the process.StatesEach stage has a number of states associated with it. Depending what decisions are made in one stage, the system might end up in different states in the next stage. If a geographical region corresponds to a stage then the states associated with it could be some particular locations (cities, warehouses, etc.) in that region. In other situations a state might correspond to amounts of certain resources which are essential for optimizing the system.DecisionsMaking decisions at one stage transforms one state of the current stage into a state in the next stage. In a geographical example, it could be a decision to go from one city to another. In resource allocation problems, it might be a decision to create or spend a certain amount of a resource. For example, in the shortest path problem three different decisions are possible to make at the state corresponding to Columbus; these decisions correspond to the three arrows going from Columbus to the three states (cities) of the next stage: Kansas City, Omaha, and Dallas.Optimal Policy and Principle of OptimalityThe goal of the solution procedure is to find an optimal policy for the overall problem, i.e., an optimal policy decision at each stage for each of the possible states. Given the current state, the optimal decision for each of the remaining states does not depend on the previous states or decisions. This is known as the principle of optimality for dynamic programming. For example, in the geographical setting the principle works as follows: the optimal route from a current city to the final destination does not depend on the way we got to the city. A system can be formulated as a dynamic programming problem only if the principle of optimality holds for it.A typical example: Shortest Path•Ben plans to drive from NY to LA•Has friends in several cities•After 1 day’s driving can reach Columbus, Nashville, or Louisville•After 2 days of driving can reach Kansas City, Omaha, or Dallas•After 3 days of driving can reach Denver or San Antonio•After 4 days of driving can reach Los Angeles•The actual mileages between cities are given in the figure (next slide)•Where should Ben spend each night of the trip to minimize the number of miles traveled?Shortest Path: network figureNew York1New York1Columbus2Columbus2Kansas City5Kansas City5Denver8Denver8Los Angeles10Los Angeles10Omaha6Omaha6Dallas7Dallas7Nashville3Nashville3Louisville4Louisville4San Antonio9San Antonio9Stage 1Stage 1Stage 2Stage 2Stage 3Stage 3Stage 4Stage 4Stage 5Stage 5550680610103013902707909405407907901050580660510830700770900 760Shortest Path problem: Solution•The problem is solved recursively by working backward in the network•Let cij be the mileage between cities i and j •Let ft(i) be the length of the shortest path from city i to LA (city i is in stage t)Stage 4 computations are obvious:•f4(8) = 1030•f4(9) = 1390Shortest Path: network figureNew York1New York1Columbus2Columbus2Kansas City5Kansas City5Denver8Denver8Los Angeles10Los Angeles10Omaha6Omaha6Dallas7Dallas7Nashville3Nashville3Louisville4Louisville4San Antonio9San Antonio9Stage 1Stage 1Stage 2Stage 2Stage 3Stage 3Stage 4Stage 4Stage 5Stage 5550680610103013902707909405407907901050580660510830700770900 760Stage 3 computationsWork backward one stage (to stage 3 cities) and find the shortest path to LA from each stage 3 city.To determine f3(5), note that the shortest path from city 5 to LA must be one of the following:• Path 1: Go from city 5 to city 8 and then take the shortest path from city 8 to city 10.• Path 2: Go from city 5 to city 9 and then take the shortest path from city 9 to city 10. f3(5) minc58 f4(8) 610 1030 1640 *c59 f4(9) 790 1390 2180f3(6) minc68 f4(8) 540 1030 1570 *c69 f4(9) 940 1390 2330f3(7) minc78 f4(8) 790 1030 1820c79 f4(9) 270 1390 1660 *Similarly,Shortest Path: network figureNew York1New York1Columbus2Columbus2Kansas City5Kansas City5Denver8Denver8Los Angeles10Los Angeles10Omaha6Omaha6Dallas7Dallas7Nashville3Nashville3Louisville4Louisville4San Antonio9San Antonio9Stage 1Stage 1Stage 2Stage 2Stage 3Stage 3Stage 4Stage 4Stage 5Stage 5550680610103013902707909405407907901050580660510830700770900 760Stage 2 computationsWork backward one stage (to stage 2 cities) and find the shortest path to LA from each stage 2 city. f2(2) mi nc25 f3(5) 680 1640 2320 *c26 f3(6) 790
View Full Document
Unlocking...