动态规划-石子合并.ppt

动态规划思想：石子合并问题,信工2013020441,问题描述,在一个圆形操场的四周摆放着n 堆石子,现要将石子有次序地合并成一堆。 规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。,此问题的三个版本,任意版：有N堆石子，现要将石子有序的合并成一堆，每次只能移动任意的2堆石子合并，合并花费为将的一堆石子的数量。 (贪心算法，哈夫曼编码问题) 直线版：在一条直线上摆着N堆石子，其余条件不变。 圆形版：石子是排成圆形，其余条件不变。,问题初步分析,如果N1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N1次合并后的得分总和必然是最优的。 此我们需要通过动态规划算法来求出最优解。,信工2013020441,信工2013020441,问题具体分析,设m(i,j)定义为第i堆石子到第j堆石子合并后的最少总分数。a(i)为第i堆石子得石子数量。 当合并的石子堆为1堆时，很明显m(i,i)的分数为0; 当合并的石子堆为2堆时，m(i,i+1)的分数为a(i)+a(i+1); 当合并的石子堆为3堆时，m(i,i+2)的分数为 MIN(m(i,i)+m(i+1,i+2)+sum(i,i+2),(m(i,i+1)+m(i+2,i+2)+sum(i,i+2); 当合并的石子堆为4堆时,动态规划通项,通项式 aij = mink | aik + ak+1j + sumi.j, k = i.j-1 （？） 其中aij表示从第i堆到第j堆合并能够取到的最小值，将其分解为两部分，从i到k，以及从k+1到j，再加上两大堆合并的得分。,部分关键代码1,int MatrixChain_min(int pN,int n) /定义二维数组mij来记录i到j的合并过成中最少石子数目 /此处赋值为-1 int mNN; /初始化 for(int x=1;x=n;x+) for(int z=1;z=n;z+) mxz=-1; int min=0; for(int g = 1;g=n;g+) mgg=0; /主对角线 for(int i=1;i=n-1;i+) int j=i+1; mij=pi+pj; ,for(int r=3; r=n;r+) for(int i=1;i=n-r+1;i+) int j = i+r-1; int sum=0; for(int b=i;b=j;b+) /最后一次合并的等分 sum+=pb; mij = mi+1j+sum; /其中一种情况 /除上面一种组合情况外的其他组合情况 for(int k=i+1;kj;k+) int t=mik+mk+1j+sum; if(tmij) mij = t; /最终得到最优解 min=m1n; return min; ,部分关键代码2,int main() int stoneN; min= MatrixChain_min(stone,n); max= MatrixChain_max(stone,n); /将前面简化的问题重新考虑进来，将圆转化为n个线性序列 for(int j=1;jmax) max=max_cache; ,程序运行结果,复杂度分析,线性时为O(n2),环形时为O(n3) DP优化 重构DP,优化方案1,DP优化 GarsiaWachs算法可以把时间复杂度压缩到O(nlogn) The Art of Computer Programming第3卷6.2.2节 概要：设一个序列是A0n-1，每次寻找最小的一个满足Ak-1Ak+Ak-1的j,把合并后的值Ak+Ak-1插入Aj的后面。 基本思想是通过树的最优性得到一个节点间深度的约束，之后证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的深度不会改变 有此定理保证，如此操作后问题的答案不会改变。,一个例子,A-1 186 64 35 32 103 An 因为35103，所以最小的k是3，我们先把35和32删除，得到他们的和67，并向前寻找一个第一个超过67的数，把67插入到他后面 186 67 64 103 因为67103，所以k=2,67和64被删除了，和131应当放在186后 186 131 103 同上述操作，现在k=2（别忘了，还有A-1和An等于正无穷大） 234 186 420 最后的答案就是各次合并的重量之和 420+234+131+67=852。,优化方案2,重构DP 以(i，j)表示一个从第i堆数起，顺时针数j堆时的子序列 (双参数DP，O(n2) 最佳合并方案包括两个信息： 在该子序列的各堆石子合并成一堆的过程中，各次合并得分的总和 形成最佳得分和的子序列和子序列。由于两个子序列是相邻的， 因此只需记住子序列的堆数 设: f(i，j)将子序列(i，j)中的j堆石子合并成一堆的最佳得分和 c(i，j)将(i，j)一分为二，其中子序列的堆数 (iN，jN),fi， ci， （iN） f，f，fN，(sum(i,i+1) c，c，cN， (1) f，N，f，N，fN