动态规划-石子合并

《动态规划-石子合并》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划思想：石子合并问题信工2013020441问题描述在一个圆形操场的四周摆放着n堆石子,现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。此问题的三个版本任意版：有N堆石子，现要将石子有序的合并成一堆，每次只能移动任意的2堆石子合并，合并花费为将的一堆石子的数量。(贪心算法，哈夫曼编码问题)直线版：在一条直线上摆着N堆石子，其余条件不变。圆形版：石子是排成圆形，其余条件不变。问题初步分析如果N－1次合并的全局最优解包含了每一次合并的子

2、问题的最优解，那么经这样的N－1次合并后的得分总和必然是最优的。此我们需要通过动态规划算法来求出最优解。信工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));当

3、合并的石子堆为4堆时......动态规划通项通项式a[i][j]=min{k

4、a[i][k]+a[k+1][j]+sum[i...j],k=i...j-1}（？）其中a[i][j]表示从第i堆到第j堆合并能够取到的最小值，将其分解为两部分，从i到k，以及从k+1到j，再加上两大堆合并的得分。部分关键代码1intMatrixChain_min(intp[N],intn){//定义二维数组m[i][j]来记录i到j的合并过成中最少石子数目//此处赋值为-1intm[N][N];//初始化for(intx=1;x<=n;x++)for(intz=1;z<=n;z++){

5、m[x][z]=-1;}intmin=0;for(intg=1;g<=n;g++)m[g][g]=0;//主对角线for(inti=1;i<=n-1;i++){intj=i+1;m[i][j]=p[i]+p[j];}for(intr=3;r<=n;r++)for(inti=1;i<=n-r+1;i++){intj=i+r-1;intsum=0;for(intb=i;b<=j;b++)//最后一次合并的等分sum+=p[b];m[i][j]=m[i+1][j]+sum;//其中一种情况//除上面一种组合情况外的其他组合情况for(intk=i+1;k

6、intt=m[i][k]+m[k+1][j]+sum;if(t

7、<=n;k++){stone[k-1]=stone[k];}stone[n]=cache;min_cache=MatrixChain_min(stone,n);max_cache=MatrixChain_max(stone,n);if(min_cachemax)max=max_cache;}···}程序运行结果复杂度分析线性时为O(n^2),环形时为O(n^3)DP优化重构DP优化方案1DP优化GarsiaWachs算法可以把时间复杂度压缩到O(nlogn)《TheArtofComputerProgr

8、amming》第3卷6.2.2节概要：设一个序列是A[0..n-1]，每次寻找最小的一个满足A[k-1]<=A[k+1]的k，(方便起见设A[-1]和A[n]等于正无穷大)那么我们就把A[k]与A[k-1]合并，之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。基本思想是通过树的最优性得到一个节点间深度的约束，之后证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的深度不会改变有此定理保证，如此操作后问题的答案不会改变。一个例子A[-1]186643532103A[n]因为35<103

9、，所以最小