1207122113 胡文峰 实验三-1动态规划.doc

算法设计与分析实验报告

学号
1207122113
姓名
胡文峰
班级
12软金1
上课地点
1-307
教师
王大寒
上课时间
2015/4/8
实验四动态规划
1. 实验目的
;
。
2. 实验环境
Eclipse, C++
Window XP
3. 实验内容
1、石子合并问题,参考矩阵连乘的动态规划解法实现石子合并问题,并分析算法的时间复杂度。
2、优化石子合并问题的动态规划算法,将算法复杂度从O(n3)降到O(n2) 。
4. 教师批改意见
签字:
成绩
日期:
实验报告细表
1实验题目
算法设计思想
本题初看以为可以使用贪心法解决问题,但是事实上因为有必须相邻两堆才能合并这个条件在,用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。例如下面这个例子:
6
3 4 6 5 4 2
如果使用贪心法求最小得分,应该是如下的合并步骤:
第一次合并 3 4 6 5 4 2 2,3合并得分是5
第二次合并 5 4 6 5 4 5,4合并得分是9
第三次合并 9 6 5 4 5,4合并得分是9
第四次合并 9 6 9 9,6合并得分是15
第五次合并 15 9 15,9合并得分是24
总得分=5+9+9+15+24=62
但是如果采用如下合并方法,却可以得到比上面得分更少的方法:
第一次合并 3 4 6 5 4 2 3,4合并得分是7
第二次合并 7 6 5 4 2 7,6合并得分是13
第三次合并 13 5 4 2 4,2合并得分是6
第四次合并 13 5 6 5,6合并得分是11
第五次合并 13 11 13,11合并得分是24
总得分=7+13+6+11+24=61
由此我们知道本题是不可以使用贪心法求解的,上例中第五次合并石子数分别为13和11的相邻两堆。这两堆石头分别由最初的第1,2,3堆(石头数分别为3,4,6)和第4,5,6堆(石头数分别为5,4,2)经4次合并后形成的。于是问题又归结为如何使得这两个子序列的N-2次合并的得分总和最优。为了实现这一目标,我们将第1个序列又一分为二:第1、2堆构成子序列1,第3堆为子序列2。第一次合并子序列1中的两堆,得分7;第二次再将之与子序列2的一堆合并,得分13。显然对于第1个子序列来说,这样的合并方案是最优的。同样,我们将第2个子序列也一分为二;第4堆为子序列1,第5,6堆构成子序列2。第三次合并子序列2中的2堆,得分6;第四次再将之与子序列1中的一堆合并,得分13。显然对于第二个子序列来说,这样的合并方案也是最优的。由此得出一个结论──6堆石子经过这样的5次合并后,得分的总和最小。
动态规划思路:
阶段i:石子的每一次合并过程,先两两合并,再三三合并,...最后N堆合并
状态s:每一阶段中各个不同合并方法的石子合并总得分。
决策:把当前阶段的合并方法细分成前一阶段已计算出的方法,选择其中的最优方案
具体来说我们应该定义一个数组s[i,j]用来表示合并方法,i表示从编号为i的石头开始合并,j表示从i开始数j堆进行合并,s[i,j]为合并的最优得分。
对于上面的例子