动态规划应用例：飞行计划.ppt

第五章动态规划及其应用,经典名句：做过了就不要再做,本周POJ上做题：动态规划,1037Adecorativefence、1050TotheMax、1088滑雪、1125StockbrokerGrapevine、1141BracketsSequence、1159Palindrome、1160PostOffice、1163TheTriangle、1458CommonSubsequence、1579FunctionRunFun、1887TestingtheCATCHER、1953WorldCupNoise、2386LakeCounting,动态规划是1951年由美国数学家贝尔曼（RichardBellman)提出，它是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径。动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种类型：离散确定型、离散随机型、连续确定型和连续随机型。,几类算法的经典名言,动态规划：不做重复的事；贪心法：只选最好的；分支定界法：没戏的就杀掉；回溯法：碰壁就回头。,作人生规划要善于利用动态规划；找女朋友要善于利用好贪心算法；人生重大决策要活学活用回溯法；,算法总体思想,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,为什么动态规划比递归算法有效？,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次，因此利用递归算法得到的算法往往是指数复杂度的算法。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,POJ2753Fibonacci数列例子：,确定Fibonaccisequencefn项的值:考虑Fibonaccisequence的递归定义:我们将得到如下的递归算法:,在POJ上递交之后，返回的结果是：TimeLimited。而不是可爱的AC,子问题的重叠性,将上述递归算法展开:可以看出f(n-1)被调用1次,f(n-2)被调用2次,等等.这将导致大量的调用最终解为：,树形递归,计算过程中存在冗余计算，为了除去冗余计算，可以从已知条件开始计算，并记录计算过程中的中间结果。,动态规划,例：POJ2753Fibonacci数列intfn+1;f1=f2=1;intI;for(i=3;i=n;i+)fi=fi-1+fi-2;coutfnendl;用空间换时间,动态规划算法的基本要素,一、最优子结构,一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其为最优子结构性质。,同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,例如：最短路径问题。abc,在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,动态规划算法的基本要素,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。,动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。,通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,一、例子（最短路问题）,假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从A地运往E地，中间通过B、C、D三个区域，在区域内有多条路径可走，现求一条由A到E的线路，使总距离最短（或总费用最小）。,将该问题划分为4个阶段的决策问题第一阶段为从A到Bj（j=1，2，3），有三种决策方案可供选择；第二阶段为从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，同理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的最短路线。,从引例的求解过程可以得到以下启示：,对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的决策过程相同的多个阶段决策问题。,所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：,在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。决策过程是与阶段发展过程逆向而行。,实例POJ2122：FlightPlanning,Yourjobistowriteaprogramthatplansairplaneflights.Eachflightconsistsofaseriesofoneormorelegs.Yourprogrammustchoosethebestaltitudeforeachlegtominimizetheamountoffuelconsumptionduringthetrip.,Theairplanehasafixedairspeed,givenbytheconstantVCRUISE,andamost-efficientcruisingaltitude,AOPT.WhenflyingataltitudeAOPT,fuelconsumptioningallonsperhourisgivenbyGPHOPT.WhenflyingatanaltitudethatisdifferentfromAOPT,fuelconsumptionincreasesbyGPHEXTRAforeach1000feetaboveorbelowAOPT.,Theflightstartsandfinishesatanaltitudeof0.Each1000footclimbburnsanextraamountoffuelgivenbyCLIMBCOST(thereisnoreductioninfuelconsumptionwhenyoudescend).Maketheapproximationthatallclimbinganddescendingisdoneinzerotimeatthebeginningofeachflightleg.,Thuseachlegisflownataconstantairspeedandaltitude.Forthisproblem,theairplanecharacteristicsaregivenbythefollowingconstants:,VCRUISE400knots(aknotisonenauticalmile(1.852km)perhour)AOPT30,000feetGPHOPT2000gallonsperhourGPHEXTRA10gallonsperhourforeach1000feetCLIMBCOST50gallonsper1000feetofclimb,Beforeeachflight,youaregiventhelengthofeachlegandthetailwindexpectedforeachleg.Apositivetailwindincreasestheairplanesspeedovertheground,andanegativetailwinddecreasesitsspeedovertheground.Forexample,ifairspeedis400knotsandthetailwindis-50knots,speedoverthegroundis350knots.,Bypolicy,altitudeforeachlegmustbesomeintegermultipleof1000feet,between20,000and40,000feet,inclusive.Yourprogrammustcomputethebestaltitudeforeachlegtominimizeoverallfuelconsumptionforthetrip,andmustcomputethefuelrequiredforthetrip.,InputThefirstlinecontainsanintegerN,representingthenumberofflightsyouarerequiredtoplan.Eachflightconsistsofthefollowinginputlines:ThefirstinputlineinaflightcontainsanintegerK(0K10),representingthenumberoflegsintheflight.ThenextKinputlineseachcontainthefollowingthreeintegers:(1)Thelengthoftheleg,innauticalmiles(2)Theexpectedtailwindat20,000feet,inknots(3)Theexpectedtailwindat40,000feet,inknots,Theexpectedtailwindataltitudesbetween20,000and40,000feetiscomputedbylinearinterpolation.Forexample,theexpectedtailwindat30,000feetishalfwaybetweentheexpectedtailwindat20,000feetandtheexpectedtailwindat40,000feet.,OutputYourprogrammustproduceoneoutputlineforeachflight.Theoutputlinemustcontaintheflightnumber(countingfromthebeginningoftheproblem),thechosenaltitudeforeachleg(inthousandsoffeet),andthefuelrequiredforthetrip(ingallons,tothenearestgallon).,图例：,转换为多段图问题,FlightPlan可以转换为多段图问题，每一条边代表某段由前一段飞行高度飞到本段的某一飞行高度的燃油消耗量,Analysis,一、计算飞机在地域i的耗油量假设飞机在地域i-1（2ik+1）的海拔高度为l，飞到地域i的海拔高度为m，计算飞机在地域i的耗油量gi,l,m必须考虑如下几个因素：（注意：为了方便计算，飞行高度和风速以1000feet为单位）1.上升过程增加的耗油量a由于飞机每上升一个单位，需要增加climbcost的耗油量，因此,Analysis,2.每小时的实际耗油量b飞机在海拔高度aopt飞行时每小时耗油gphopt.当飞机在m高度飞行时，与aopt的垂直距离为个单位。每垂直偏离aopt高度一个单位，需要增加耗油量gphextra.因此,3.在地域i的实际飞行时间cc=地域i的长度/地域i的实际飞行速度由于地域i的风速垂直反向线性变化，m单位处的风速为在20单位处的风速与40单位处的风速的平均数，因此地域i的等高风速为,而飞机的实际速度为VCRUISE与地域i等高风速的矢量和，因此c=地域i的长度/(地域i的等高风速VCRUISE)显而易见，,二规划飞行方案设为在确定地域i的飞行高度为j的情况下，飞机由地域l飞至地域i所耗费的最小总耗油量；为记忆表。飞机由地域i-l的高度到达地域i的j高度，可使总耗油量最小，即,问题是怎么才能计算呢？首先我们必须明确，按最优性要求确定了飞机在地域i-1的飞行为高度为;由于为一个定值，因此的值必须最小。不然的话，将它替换到表达式中，则可使表达式值变得更小，出现矛盾，这就说明问题的最优解包含了子问题的最优解，即该问题具备了最优子结构。,下面我们来分析一下最优表达式的构造：飞机由地域1起飞，因此data1,j=g1,0,j(20j40).然后顺序计算，data2,20data2,40,data3,20,data3,40,.datak,20,datak,40.,在计算datai,j时，我们无法预计飞机在地域i-1应以怎样的高度飞行方可使表达式的值最小。因此只能一一假设飞机在地域i-1的高度为20,21,40,即分别求出从上述21个表达式中选出值最小的一个，即：将满足上式的飞行高度L存入记忆表data2i