动态规划.ppt

动态规划95844第6章动态规划
1. 动态规划的思想
2. 采用动态规划解决问题的先决条件
3. 动态规划法求解的一般步骤
4. 动态规划法示例
5. 动态规划法总结
1. 动态规划的思想
有一类问题,它们的活动过程往往划分为若干阶段,每一阶段决策依赖于前一阶段的状态,由决策所采取的动作使状态发生转移,成为下一阶段的依据
动态规划方法试图在每一个阶段上按照前一阶段的状态决定自己的选择;如果本阶段不知道哪个状态是否最优,那么它会把它所掌握的信息转告给下一阶段
动态规划就是累积各阶段的最优,以达到全局的最优
2. 采用动态规划解决问题的先决条件
问题可以分阶段
满足最优性原理:无论过程的初始状态和初始决策是什么,其余决策都必须相对于初始决策产生的状态,构成一个最优决策序列
3. 动态规划法求解的一般步骤
明确划分问题的阶段
从问题的初始端或终结端开始,分阶段依次进行最优状态选择
从另一端开始回溯,确定全局最优解包含哪些阶段性选择
4. 动态规划法示例
钓鱼问题
多段图最短路径问题
资源分配问题
最长公共子序列问题
最长不升自序列问题
0/1背包问题
村庄和邮局问题
最大子段和问题
钓鱼问题
钓鱼问题的描述
钓鱼问题的动态规划解法示例
钓鱼问题的动态规划解法的步骤
动态规划解决钓鱼问题的复杂度分析
钓鱼问题的描述
钓鱼者要从n [20, 40]个池塘中钓鱼。这些池塘在一条直线上,从一个池塘移动到另一个池塘需要1个时间单位;一个时间单位之中该人能够从池塘j中钓到鱼fj条,但下一个时间单位内能钓到鱼的数量会按照某个函数递减。给定若干个时间单位[100, 300],该钓鱼者能够最多钓到多少条鱼?
……
钓鱼问题的动态规划解法示例
池塘 1 2 3
第1时 30 20 50
第2时 15 17 20
第3时 0 13 5
分配8个时间段:先对第1池塘:
花费时间1,最大收益是30;花费时间2,最大收益是45;
花费时间3,最大收益是45;。。。。。。
对第2池塘
花费时间1;最大收益max{30+0, 0+0}—对应时间1+0+0;0+1+0
花费时间2:所花费时间可以分为2+0+0,1+1+0,0+1+1三种,
其最大收益是:max{45, 30, 20} = 45
花费时间3:所花费时间可以分为3+0+0,2+1+0,1+1+1,0+1+2四种。其最大收益是:max{45+0, 45+0, 30+20, 0+37} = 50
钓鱼问题的动态规划解法的步骤
按照池塘把决策问题划分为若干个阶段
每个阶段有若干个状态:到当前状态(移动到某个池塘)时,总共花费了多少时间
到当前池塘每一种花费时间的情况有一个最大收益,这个最大收益的计算仅仅由前一个阶段的收益表和当前池塘的收益决定
到最后一个池塘花费最多的解就是问题解,按照选择回溯,就可以得到所经过的选择。例如,上面的例子最大值50=30+20,即第一个池塘花费1个时段,第2个池塘花费1个时段受益最大
动态规划解决钓鱼问题的复杂度分析
假设时间共有n段,池塘共有m个。
在每一个池塘,都要对n个时间段做加数分解,即n = 0+n = 1+(n-1) = 2+(n-2) = ……= (n-1)+1 = n+0;(n-1) = 0+(n-1) = 1 + (n-2) = ……= (n-1)+0; 2 = 2+0 = 1+1 = 0+2
每个分解可以用O(1)的时间求得结果
因此,动态规划解决钓鱼问题的时间复杂度是O(m*n2),空间复杂度是O(m*n),用于记录所经历的选择;如果不要求记录路径,而只是给出最大收益结果,则空间复杂度是O(n)