DP动态规划ACM课件.ppt
《DP动态规划ACM课件.ppt》由会员分享,可在线阅读,更多相关《DP动态规划ACM课件.ppt(45页珍藏版)》请在三一文库上搜索。
1、动态规划1,罗方炜,简介,DP是在20世纪50年代由一位卓越的美国数学家Richcard Bellman发明的。它作为一种重要的工具在应用数学中被广泛的应用。它不仅可以解决特定类型的优化问题,还可以作为一种通用的算法设计技术来使用。,DP的实质,利用问题的所具有的重叠子问题的性质进行记忆化求解。(用空间换时间),求Fibonacci数: f(n) = f(n-1) + f(n-2) n2 f(1)=f(2)=1,常规递归,int Non_DP(int n) if (n=1 | n=2) return 1; else return Non_DP(n-1) + Non_DP(n-2); 指数级时间
2、复杂度,无法忍受,两种实现方式,自底向上(bottom up) int DP_Bottom_Up(int n) memo1 = memo2 = 1; for (int i=3; i=n; i+) memoi = memoi-1 + memoi-2; return memon; ,自顶向下(top down) int DP_Top_Down(int n) if (n = 1 | n = 2) return 1; if (memon != 0) return memon; memon = DP_Top_Down(n-1) + DP_Top_Down(n-2); return memon; ,基本概
3、念,最短路问题,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E,求A到E的最短路径。,直观的方法是用回溯法搜索。时间复杂度为指数级。 低效的原因:没有充分利用重叠子问题的性质。,此图有明显的次序,可以划分为5阶段。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E,阶段0,阶段1,阶段2,阶段3,阶段4,设 Diskx 为第k阶段城市x到城市E的最短路径长度。 map i j 为i,j两个城市间的距离。 递归方程为 Diskx = min Disk+1y+mapx,y 此问题时间复杂度降为O(n2).,状态:贴切,简洁的描述出事物性质的单元量。例如:Disx。 要求:
4、状态与状态之间可以转移,以便有初始状态逐渐转移到目标状态,找到问题的解。 阶段:若干性质相近可以同时处理的状态的集合。就是计算状态的顺序。 要求:每个阶段中状态的取值只与这个阶段之前的阶段中的状态有关,与这个阶段之后的阶段中的状态无关。,状态转移方程:前一个阶段中的状态转移到后一个阶段的状态得演变规律,即相邻两个阶段的状态变化方程。 fk(i) = opt fk-1(j) + cost(i,j) k阶段的i状态与k-1阶段的j状态有关 决策:计算每个状态时作出的选择。,适合用DP解决的问题的性质,最优子结构:若求解的问题是最优化问题,则原问题最优当且仅当自问题最优。 Mod 4 最优路径问题
5、找出1到4的一条长度mod 4的余数最小的路径。,1,2,3,4,此最优化问题不满足最优子结构,所以不适合用DP。 但如果我们增加状态的维数,将最优化问题转化成判定性问题,再运用DP,问题就可得以解决。 设 fki 为bool型数组,表示从1点到k点长度mod4为i的路径是否存在。 fki= fk-1i-lenk1 | fk-1i-lenk2 | | fk-1i-lenkn,无后效性:决策之取决于当前状态的特征因素,而和到达此状态的方式无关。也就是每个阶段中状态的取值只与这个阶段之前的阶段中的状态有关,与这个阶段之后的阶段中的状态无关。 如果当前定义的状态不满足无后效性,应重新定义。,一维状态
6、存储问题,硬币问题1: 有n种硬币,每种硬币的面值为vi元,且只有一枚,问用这n种硬币找零S元的方法数。 设dij为前i种硬币组成j元的方法数。 dij = di-1j + di-1j-vi d00=1,d01S=0 空间复杂度为O(n2),浪费!,d0=1; d1S=0; for (i=1; i=vi; j-) dj += dj-vi; ,0-1背包问题: 给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大?,设m(i,j)是背包容量为j,可选择物品为i,i+1,,n时,0-1背包问题的最优值。 m(i,j)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- DP 动态 规划 ACM 课件
链接地址:https://www.31doc.com/p-2143740.html