下载此文档

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


文档分类:行业资料 | 页数:约51页 举报非法文档有奖
1/51
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/51 下载此文档
文档列表 文档介绍
第五章 动态规划及其应用
经典名句:做过了就不要再做
本周POJ上做题:动态规划
1037 A decorative fence、 1050 To the Max、 1088 滑雪、
1125 Stockbroker Grapevine、 1141 Brackets Sequence、
1159 Palindrome、 1160 Post Office、
1163 The Triangle、 mon Subsequence、
1579 Function Run Fun、 1887 Testing the CATCHER、
1953 World Cup Noise、 2386 Lake Counting
动态规划是1951年由美国数学家贝尔曼(Richard Bellman)提出,它是解决一类多阶段决策问题的优化方法,也是考察问题的一种途径。
动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题,且它的每一阶段都需进行决策,则这类问题均可用动态规划方法进行求解。
根据多阶段决策过程的时序和决策过程的演变,动态规划方法有以下四种类型:离散确定型、离散随机型、连续确定型和连续随机型。
几类算法的经典名言
动态规划:不做重复的事;
贪心法:只选最好的;
分支定界法:没戏的就杀掉;
回溯法:碰壁就回头。
作人生规划要善于利用动态规划;
找女朋友要善于利用好贪心算法;
人生重大决策要活学活用回溯法;
算法总体思想
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
为什么动态规划比递归算法有效?
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次,因此利用递归算法得到的算法往往是指数复杂度的算法。
如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
n
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
n/2
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
T(n/4)
T(n)
POJ 2753 i数列例子:
i sequence fn项的值:
i sequence的递归定义:
我们将得到如下的递归算法:
在POJ上递交之后,返回的结果是:Time Limited。而不是可爱的AC
Why?
子问题的重叠性
将上述递归算法展开:
可以看出 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)
1
1
0
0
1
0
1
0
冗余计算
动态规划
例:POJ 2753 i数列
int f[n+1];
f[1]=f[2]=1;
int I;
for(i=3;i<=n;i++)
f[i] = f[i-1]+f[i-2];
cout << f[n] <<endl;
用空间换时间

动态规划应用例-飞行计划 来自淘豆网m.daumloan.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数51
  • 收藏数0 收藏
  • 顶次数0
  • 上传人nb6785
  • 文件大小0 KB
  • 时间2015-06-12
最近更新