第四章5(贪心、动态)PPT课件.ppt

第 四 章 基本的算法策略
动态规划 认识动态规划 算法框架 突出阶段性的动态规划应用 突出递推的动态规划应用
1
编辑版pppt
在动态规划算法策略中，体现在它的决策不是线性的而是全面考虑不同的情况分别进行决策, 并通过多阶段决策来最终解决问题。在各个阶段采取决策后, 会不断决策出新的数据,, 又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义。所以，这种多阶段决策最优化的解决问题的过程称为动态规划。
上节 下节
动态规划
2
编辑版pppt
我们通过一个简单的例子来说明动态规划的多阶段决策与贪婪算法有什么区别。

【例1】 数塔问题
上节 下节
认识动态规划
3
编辑版pppt
【例1】数塔问题
有形如图4-11所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。
问题分析
算法设计
算法
小结
4
编辑版pppt
问题分析
这个问题用贪婪算法有可能会找不到真正的最大和。以图4-11为例就是如此。用贪婪的策略，则路径和分别为：
9+15+8+9+10=51 （自上而下），
19+2+10+12+9=52（自下而上）。
都得不到最优解，真正的最大和是：
9+12+10+18+10=59。
在知道数塔的全貌的前提下，可以用枚举法或下一章将学习的搜索算法来完成。
上节 下节
5
编辑版pppt
算法设计
动态规划设计过程如下：
：
第一步对于第五层的数据，我们做如下五次决策：
对经过第四层2的路径选择第五层的19，
对经过第四层18的路径选择第五层的10，
对经过第四层9的路径也选择第五层的10，
对经过第四层5的路径选择第五层的16。
上节 下节
6
编辑版pppt
以上的决策结果将五阶数塔问题变为4阶子问题，递推
出第四层与第五层的和为:
21(2+19),28(18+10),19(9+10),21(5+16)。
用同样的方法还可以将4阶数塔问题,变为3阶数塔问题。
…… 最后得到的1阶数塔问题，就是整个问题的最优解。
上节 下节
7
编辑版pppt
2．存储、求解：
1) 原始信息存储
原始信息有层数和数塔中的数据，层数用一个整型
变量n存储，数塔中的数据用二维数组data，存储成如
下的下三角阵:
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
上节 下节
8
编辑版pppt
2) 动态规划过程存储
必需用二维数组a存储各阶段的决策结果。二维数组a的存储内容如下：
d[n][j]=data[n][j] j=1,2,……,n；
i=n-1,n-2,……1，j=1,2,……,i；时
d[i][j]=max(d[i+1][j]，d[i+1][j+1])+data[i][j]
最后a[1][1]存储的就是问题的结果。
上节 下节
9
编辑版pppt
3) 最优解路径求解及存储
仅有数组data和数组a可以找到最优解的路径， 但需要自顶向下比较数组data和数组a是可以找到。：
上节