2019年 动态规划应用例飞行计划 ppt课件.ppt

《2019年 动态规划应用例飞行计划 ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章动态规划及其应用经典名句：做过了就不要再做本周POJ上做题：动态规划1037Adecorativefence、1050TotheMax、1088滑雪、1125StockbrokerGrapevine、1141BracketsSequence、1159Palindrome、1160PostOffice、1163TheTriangle、1458CommonSubsequence、1579FunctionRunFun、1887TestingtheCATCHER、1953WorldCupNois

2、e、2386LakeCounting动态规划是1951年由美国数学家贝尔曼（RichardBellman)提出，它是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径。动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种类型：离散确定型、离散随机型、连续确定型和连续随机型。几类算法的经典名言动态规划：不做重复的事；贪心

3、法：只选最好的；分支定界法：没戏的就杀掉；回溯法：碰壁就回头。作人生规划要善于利用动态规划；找女朋友要善于利用好贪心算法；人生重大决策要活学活用回溯法；算法总体思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=为什么动态规划比递归算法有效？但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次，因此利用递归算法得到的算法往往是指数复杂度的算法。如果能够

4、保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)POJ2753Fibonacci数列例子：确定Fibonaccisequencefn项的值:考虑Fibonaccisequence的递归定义:我们将得到如下的递归算法:在POJ上递交之后，返回的结果是：TimeLimited。而不是可爱

5、的ACWhy？子问题的重叠性将上述递归算法展开:可以看出f(n-1)被调用1次,f(n-2)被调用2次,等等.这将导致大量的调用最终解为：树形递归计算过程中存在冗余计算，为了除去冗余计算，可以从已知条件开始计算，并记录计算过程中的中间结果。f(5)f(3)f(2)f(1)f(2)f(4)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)f(1)11001010冗余计算动态规划例：POJ2753Fibonacci数列intf[n+1];f[1]=f[2]=1;intI;for(i=3;i<=

6、n;i++)f[i]=f[i-1]+f[i-2];cout<

7、性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。动态规划算法的基本要素二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。一、例子

8、（最短路问题）假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从A地运往E地，中间通过B、C、D三个区域，在区域内有多条路径可走，现求一条由A到E的线路，使总距离最短（或总费用最小）。AB1B2B3C1C2C3D1D2E24374632426534633334将该问题划分为4个阶段的决策问题第一阶段为从A到Bj（j=1，2，3），有三种决策方案可供选择；第二阶段为从Bj到Cj（j=1,2,3），也