Transcription of Dynamic Programming Examples - cvut.cz
{{id}} {{{paragraph}}}
Example: biology
Dynamic Programming Examples - cvut.cz
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: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
Dynamic Programming Examples 1. Minimum cost from Sydney to Perth 2. Economic Feasibility Study 3. 0/1 Knapsack problem 4. Sequence Alignment problem
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: