- 2020-06-04 00:34
*views 4*- C++( Data structure and algorithm )

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

- Java378 articles
- Python197 articles
- Linux110 articles
- MySQL83 articles
- Vue78 articles
- SpringBoot68 articles
- Spring61 articles
- javascript56 articles
- more...

Daily Recommendation

views 2

©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