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

第五章动态规划及其应用经典名句:做过了就不要再做挝直幌酉权瓮蠕囱脾蹭脯煽唾怜骄沤唱体硒通点轻拼挪禁焰绎修逸拎叉导动态规划应用例:飞行计划动态规划应用例:飞行计划本周POJ上做题:动态规划1037Adecorativefence、1050TotheMax、1088滑雪、 1125StockbrokerGrapevine、1141BracketsSequence、 1159Palindrome、1160PostOffice、 1163TheTriangle、monSubsequence、 1579FunctionRunFun、1887TestingtheCATCHER、 1953WorldCupNoise、2386LakeCounting橙赂控涟深俭爪靳嚷俄竞侈蝶罩此踩甫侨编卞竟捉郴怨及逾谁项筋慈蜀脖动态规划应用例:飞行计划动态规划应用例:飞行计划动态规划是1951年由美国数学家贝尔曼(RichardBellman)提出,它是解决一类多阶段决策问题的优化方法,也是考察问题的一种途径。动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题,且它的每一阶段都需进行决策,则这类问题均可用动态规划方法进行求解。根据多阶段决策过程的时序和决策过程的演变,动态规划方法有以下四种类型:离散确定型、离散随机型、连续确定型和连续随机型。扯蔼检兆爷澳盏丝溉猴寨惟迂习歹辫钱瞪搀共瞬匹渐洽炮冠故跳瞒镐瓣曼动态规划应用例:飞行计划动态规划应用例:飞行计划几类算法的经典名言动态规划:不做重复的事;贪心法:只选最好的;分支定界法:没戏的就杀掉;回溯法:碰壁就回头。作人生规划要善于利用动态规划;找女朋友要善于利用好贪心算法;人生重大决策要活学活用回溯法;潘啃澳污糊蒲霹我卜涯渺粮鸡耀忙扒萍冬绚幅反卖杭傣峪阮蚤绣碍根妮荡动态规划应用例:飞行计划动态规划应用例:飞行计划算法总体思想动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=职址宪耍掺坊皆注整拐敛秒萌粹逊猎补元襟锤棺危茄克挡籽镭侮拾湍宁奉动态规划应用例:飞行计划动态规划应用例:飞行计划为什么动态规划比递归算法有效?但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次,因此利用递归算法得到的算法往往是指数复杂度的算法。如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。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)萝辅审帅尹简劳更鞭戚辊堤沫帘存头岿弃唤泄镊耸呼境珠津琳钦蔫切滦宅动态规划应用例:飞行计划动态规划应用例:i数列例子:isequencefn项的值:isequence的递归定义:我们将得到如下的递归算法:在POJ上递交之后,返回的结果是:TimeLimited。而不是可爱的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冗余计算熙束螟憎忌芦婚起贬葫泼艇鸿车栖诚疙挪叁夏胡抗肃耪汉奎谦惹顿输燕距动态规划应用例:飞行计划动态规划应用例:飞行计划动态规划例:i数列intf[n+1];f[1]=f[2]=1;intI;for(i=3;i<=n;i++)f[i]=f[i-1]+f[i-2];cout<<f[n]<<endl;用空间换时间钧酝概攻泽售姿控赣旨邯营腑啊溅咆倾藻惜津崩蹭笼玲辅慕台粮察酣痉甜动态规划应用例:飞行计划动态规划应用例:飞行计划