《动态规划应用例：飞行计划.ppt》由会员分享，可在线阅读，更多相关《动态规划应用例：飞行计划.ppt（49页珍藏版）》请在三一办公上搜索。
1、第五章动态规划及其应用,经典名句：做过了就不要再做,本周POJ上做题：动态规划,1037 A decorative fence、1050 To the Max、1088 滑雪、1125 Stockbroker Grapevine、1141 Brackets Sequence、1159 Palindrome、1160 Post Office、1163 The Triangle、1458 Common Subsequence、1579 Function Run Fun、1887 Testing the CATCHER、1953 World Cup Noise、2386 Lake Counting,
2、动态规划是1951年由美国数学家贝尔曼（Richard Bellman)提出，它是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径。动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种类型：离散确定型、离散随机型、连续确定型和连续随机型。,几类算法的经典名言,动态规划：不做重复的事；贪心法：只选最好的；分支定界法：没戏的就杀掉；回溯法：碰壁就回头。,作人生规划要善于利用动态规划；找女朋友要善于利用好贪心算法；
3、人生重大决策要活学活用回溯法；,算法总体思想,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,为什么动态规划比递归算法有效？,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次，因此利用递归算法得到的算法往往是指数复杂度的算法。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,POJ 2753 Fibonacci数列例子：,确定Fibonacci sequence fn项的值:考虑Fibonacci sequence的递归定义:我们将
4、得到如下的递归算法:,在POJ上递交之后，返回的结果是：Time Limited。而不是可爱的AC,子问题的重叠性,将上述递归算法展开:可以看出 f(n-1)被调用 1次,f(n-2)被调用 2次,等等.这将导致大量的调用 最终解为：,树形递归,计算过程中存在冗余计算，为了除去冗余计算，可以从已知条件开始计算，并记录计算过程中的中间结果。,动态规划,例：POJ 2753 Fibonacci数列int fn+1;f1=f2=1;int I;for(i=3;i=n;i+)fi=fi-1+fi-2;cout fn endl;用空间换时间,动态规划算法的基本要素,一、最优子结构,一个最优化策略具有这样
5、的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其为最优子结构性质。,同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,例如：最短路径问题。a b c,在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,动态规划算法的基本要素,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复
6、计算多次。这种性质称为子问题的重叠性质。,动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。,通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,一、例子（最短路问题）,假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从A地运往E地，中间通过B、C、D三个区域，在区域内有多条路径可走，现求一条由A到E的线路，使总距离最短（或总费用最小）。,将该问题划分为4个阶段的决策问题第一阶段为从A到Bj（j=1，2，3），有三种决策方
7、案可供选择；第二阶段为从Bj到Cj（j=1,2,3），也有三种方案可供选择；第三阶段为从Cj到Dj(j=1,2)，有两种方案可供选择；第四阶段为从Dj到E，只有一种方案选择。,如果用完全枚举法，则可供选择的路线有3321=18（条），将其一一比较才可找出最短路线：AB1C2D3E其长度为12。,显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点：,第四阶段，由D1到E只有一条路线，其长度f4（D1）=3
8、，同理f4（D2）=4。第三阶段，由Cj到Di分别均有两种选择，即,，决策点为D1,决策点为D1,，决策点为D2,第二阶段，由Bj到Cj分别均有三种选择，即：,决策点为C2,决策点为C1或C2,决策点为C2,第一阶段，由A到B，有三种选择，即：,决策点为B3,f1（A）=15说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即AB3C2D2E上述最短路线问题的计算过程，也可借助于图形直观的表示出来：,图中各点上方框的数，表示该点到E的最短距离。图中红箭线表示从A到E的最短路线。,从引例的求解过程可以得到以下启示：,对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系
9、的决策过程相同的多个阶段决策问题。,所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：,在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。决策过程是与阶段发展过程逆向而行。,实例POJ2122：Flight Planning,Your job is to write a program that p
10、lans airplane flights.Each flight consists of a series of one or more legs.Your program must choose the best altitude for each leg to minimize the amount of fuel consumption during the trip.,The airplane has a fixed airspeed,given by the constant VCRUISE,and a most-efficient cruising altitude,AOPT.W
11、hen flying at altitude AOPT,fuel consumption in gallons per hour is given by GPHOPT.When flying at an altitude that is different from AOPT,fuel consumption increases by GPHEXTRA for each 1000 feet above or below AOPT.,The flight starts and finishes at an altitude of 0.Each 1000 foot climb burns an e
12、xtra amount of fuel given by CLIMBCOST(there is no reduction in fuel consumption when you descend).Make the approximation that all climbing and descending is done in zero time at the beginning of each flight leg.,Thus each leg is flown at a constant airspeed and altitude.For this problem,the airplan
13、e characteristics are given by the following constants:,VCRUISE 400 knots(a knot is one nautical mile(1.852km)per hour)AOPT 30,000 feetGPHOPT 2000 gallons per hourGPHEXTRA 10 gallons per hour for each 1000 feetCLIMBCOST 50 gallons per 1000 feet of climb,Before each flight,you are given the length of
14、 each leg and the tailwind expected for each leg.A positive tailwind increases the airplanes speed over the ground,and a negative tailwind decreases its speed over the ground.For example,if airspeed is 400 knots and the tailwind is-50 knots,speed over the ground is 350 knots.,By policy,altitude for
15、each leg must be some integer multiple of 1000 feet,between 20,000 and 40,000 feet,inclusive.Your program must compute the best altitude for each leg to minimize overall fuel consumption for the trip,and must compute the fuel required for the trip.,InputThe first line contains an integer N,represent
16、ing the number of flights you are required to plan.Each flight consists of the following input lines:The first input line in a flight contains an integer K(0 K 10),representing the number of legs in the flight.The next K input lines each contain the following three integers:(1)The length of the leg,
17、in nautical miles(2)The expected tailwind at 20,000 feet,in knots(3)The expected tailwind at 40,000 feet,in knots,The expected tailwind at altitudes between 20,000 and 40,000 feet is computed by linear interpolation.For example,the expected tailwind at 30,000 feet is halfway between the expected tai
18、lwind at 20,000 feet and the expected tailwind at 40,000 feet.,OutputYour program must produce one output line for each flight.The output line must contain the flight number(counting from the beginning of the problem),the chosen altitude for each leg(in thousands of feet),and the fuel required for t
19、he trip(in gallons,to the nearest gallon).,图例：,转换为多段图问题,Flight Plan可以转换为多段图问题，每一条边代表某段由前一段飞行高度飞到本段的某一飞行高度的燃油消耗量,Analysis,一、计算飞机在地域i的耗油量 假设飞机在地域i-1（2ik+1）的海拔高度为l，飞到地域i的海拔高度为m，计算飞机在地域i的耗油量gi,l,m必须考虑如下几个因素：（注意：为了方便计算，飞行高度和风速以1000feet为单位）1.上升过程增加的耗油量a 由于飞机每上升一个单位，需要增加climbcost的耗油量，因此,Analysis,2.每小时的实际耗油
20、量b 飞机在海拔高度aopt飞行时每小时耗油gphopt.当飞机在m高度飞行时，与aopt的垂直距离为 个单位。每垂直偏离aopt高度一个单位，需要增加耗油量gphextra.因此,3.在地域i的实际飞行时间c c=地域i的长度/地域i的实际飞行速度 由于地域i的风速垂直反向线性变化，m单位处的风速为在20单位处的风速与40单位处的风速的平均数，因此地域i的等高风速为,而飞机的实际速度为VCRUISE与地域i等高风速的矢量和，因此 c=地域i的长度/(地域i的等高风速VCRUISE)显而易见，,二规划飞行方案 设 为在确定地域i的飞行高度为j的情况下，飞机由地域l飞至地域i所耗费的最小总耗油量
21、；为记忆表。飞机由地域i-l的 高度到达地域i的j高度，可使总耗油量最小，即,问题是怎么才能计算 呢？首先我们必须明确，按最优性要求确定了飞机在地域i-1的飞行为高度为;由于 为一个定值，因此 的值必须最小。不然的话，将它替换到 表达式中，则可使表达式值变得更小，出现矛盾，这就说明问题的最优解包含了子问题的最优解，即该问题具备了最优子结构。,下面我们来分析一下最优表达式的构造：飞机由地域1起飞，因此data1,j=g1,0,j(20j40).然后顺序计算，data2,20 data2,40,data3,20,data3,40,.datak,20,datak,40.,在计算datai,j时，我们
22、无法预计飞机在地域i-1应以怎样的高度飞行方可使表达式的值最小。因此只能一一假设飞机在地域i-1的高度为20,21,40,即分别求出从上述21个表达式中选出值最小的一个，即：将满足上式的飞行高度L存入记忆表data2i,j,由此可见，在求datai,j的过程中不断查阅子问题的解datai-1,20.datai-1,40。显然这个最优化问题包含了重叠子问题，采用动态程序设计方法是最合适不过的了，按照上述分析，我们可以直接写出动态规划的方程：1ik 20j40 20l40,求解data表和data2表的算法十分简单：for j:=20 to 40 do data1,j g1,0,j;/*构造记忆表
23、*/for i:=2 to k do for j:=20 to 40 do for i:=20 to 40 do begin 计算datai,j=mindatai-1,l,gi,l,j;将满足上式的l记入记忆表data2i,j;end:for,三.输出飞行计划 有了记忆表data2我们便可以从地域k出发倒推飞机在各地域的飞行高度data3:for j:=20 to 40 do data3k 计算满足mindatak,j的j;for i:=k downto 2 do data3i-ldata2i,data3i;最后输出飞行计划：for i=1 to k do 输出飞机在地域i的飞行高度data3i;输出最小的总耗油量datak,data3k;每输入一条航线信息，我们便使用上述方法规划该航线的飞行方案，直至n条航线规划完毕,总结及回顾：,本次课主要讲解了如下内容：动态规划的要素；多段图问题；动态规划的求解步骤；Flight Planning。首先证明该问题满足最有性；得到递推公式和边界条件；自底向上求解；自顶向下恢复最有决策。,课后作业,编程练习题：课后编写本次课程中的Flight Planning 的程序。,
