One , The idea of dynamic planning

* The basis of dynamic programming is the optimal principle
* Dynamic programming is the same as greedy algorithm , The solution to a problem is the result of a series of choices :
* In greedy algorithm , Every decision we make according to the rule of greed is irrevocable
* In dynamic planning , We need to examine a series of choices , To determine whether an optimal decision sequence contains optimal decision subsequences
Two , The shortest path of practical application

Problem description

* We have to choose a source point s=1 To destination vertex d=5 Shortest path of

The solution of dynamic planning

* Step 1 : Vertices can be selected 2,3,4
* Step 2 : Suppose we choose the vertex 3, Then we have to decide from the top 3 Move to vertex 5
* Step 3 : If we choose one from the vertex 3 To vertex 5 Path to , But not the shortest . For example, the selected sub path is 3,2,5, Its length is 9, Then the connected path is 1,3,2,5, Its length is 11
* Step 4 : If the shortest subpath is used 3,4,5 replace 3,2,5, Then the path 1,3,4,5 The length of is 7
* therefore , We need to constantly return and re judge , Find a way to 1 reach 5 Shortest path of , Replace if not the shortest
Three , Practical application 0/1 knapsack problem

Problem description

* Yes n Items and a capacity of c Our Backpack . goods i Weight of Wi, The value is p. Now from n Select some of the items and put them in the bag
* The best requirement now is : When the total weight of the packed items does not exceed the capacity of the backpack , Maximize the total value of items
* The problem description is :

* The constraint is :

* Xi=1 Indicates that the item is loaded into the backpack ,Xi=0 Indicates the item is not in the backpack
for example

* hypothesis n=3,w=[100,14,10],p=[20,18,15],c=116
* If you choose x1=1, Then the remaining capacity is 116-100=16, So the next possible solution is :
* If the next feasible solution is [x2,x3]=[1,0], Then the total value of this time is 100+18=118
*
If the next feasible solution is [x2,x3]=[0,1], Then the value is 100+15=115. therefore ,[x2,x3]=[0,1] Not the best solution , So go back to the first step , choice x=[1,1,0] This sequence
* If you choose x1=0, Then the remaining capacity is 116, So the next possible solution is :
*
If the next feasible solution is [x2,x3]=[1,1], Then the total value of this time is 18+15=33. therefore ,[x2,x3]=[1,1] Not the best solution , So we need to go back to the beginning , Reselect x1=1, Then continue with dynamic rules
Four , Actual application of air fare

Problem description

* The price list of a certain route is :
* The fare is $100 The route of : From Atlanta to New York / Or Chicago ; Or from Los Angeles to Atlanta
* The fare is $20 The route of : From Chicago to New York ; Or for passengers passing through Atlanta , From Atlanta to Chicago
* To save money , Need to select transit Airport :
* If you use ( starting point , End ) Indicates the problem status , So after choosing Los Angeles to Atlanta , Problem state becomes ( Atlanta , New York )
* The direct fare from Atlanta to New York is $100, So the flight from Los Angeles to New York is $200
* Let the ticket price from Atlanta to Chicago to New York be $40. So Los Angeles —— Atlanta —— The total fare in New York is $140
*
If triples are used (tag, starting point , End ) Indicates the problem status , among tag by 0 Indicates a turnaround ,tag by 1 Other situations , So when we get to Atlanta , The problem status changes to (0, Atlanta , New York ), Its best route is to use Chicago as a transit Airport
Five , Recursive equation of dynamic programming

* When the optimal choice contains the optimal subsequence , Recursive equation of dynamic programming can be established , It can help us solve problems efficiently
0/1 Knapsack problem cases

* In the knapsack problem mentioned above , The optimal selection sequence consists of the most optimal subsequence
* hypothesis f(i,y) Indicates that the remaining capacity is y, The remaining items are i,i+1,...n The value of the optimal solution of knapsack problem , Namely :

* No matter what the first choice is , The next choice must be the rightmost choice in the current state , We call this “ Optimal principle
”. It means that an optimal selection sequence is composed of the optimal selection subsequence . however , The optimal principle may not be applicable to some problems , In this case, dynamic planning cannot be applied
* The steps of applying dynamic programming are as follows :
* 1) Confirm that the optimal principle is applicable
* 2) Establishing recursive equation of dynamic programming
* 3) Solving recursive equations of dynamic programming to obtain the optimal solution
* 4) Backtracking along the generation process of the optimal solution
*
It is an attractive thing to write a simple recursive equation to solve the dynamic programming equation . however , We will see in the following dynamic planning application article , If you can't avoid double counting , The complexity of recursive equations will be considerable . If double counting is avoided , Complexity will drop dramatically . The recursive equation of dynamic programming can also be solved by iterative method , In this case, the repeated calculation is naturally avoided . actually , Iterative programs have the same complexity as recursive programs that avoid repeated calculations , But iterators don't need additional recursive stack space , So it will run faster than the latter

Technology
©2019-2020 Toolsou All rights reserved,
Unity Scene loading asynchronously ( Implementation of loading interface )ESP8266/ESP32 System : Optimize system startup time vue Of v-if And v-show The difference between JS How to operate college examination for the self-taught An overview of Marxism Faster RCNN Explanation of series algorithm principle ( note )CSS architecture design NOI2019 travels IAR Installation and use tutorial sort ( one ) bubble sort