动态规划-石子合并.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,intMatrixChain_min(intpN,intn)/定义二维数组mij来记录i到j的合并过成中最少石子数目/此处赋值为-1intmNN;/初始化for(intx=1;x=n;x+)for(intz=1;z=n;z+)mxz=-1;intmin=0;for(intg=1;g=n;g+)mgg=0;/主对角线for(inti=1;i=n-1;i+)intj=i+1;mij=pi+pj;,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+=pb;mij=mi+1j+sum;/其中一种情况/除上面一种组合情况外的其他组合情况for(intk=i+1;kj;k+)intt=mik+mk+1j+sum;if(tmij)mij=t;/最终得到最优解min=m1n;returnmin;,部分关键代码2,intmain()intstoneN;min=MatrixChain_min(stone,n);max=MatrixChain_max(stone,n);/将前面简化的问题重新考虑进来，将圆转化为n个线性序列for(intj=1;jmax)max=max_cache;,程序运行结果,复杂度分析,线性时为O(n2),环形时为O(n3)DP优化重构DP,优化方案1,DP优化GarsiaWachs算法可以把时间复杂度压缩到O(nlogn)TheArtofComputerProgramming第3卷6.2.2节概要：设一个序列是A0.n-1，每次寻找最小的一个满足Ak-1Ak+Ak-1的j,把合并后的值Ak+Ak-1插入Aj的后面。基本思想是通过树的最优性得到一个节点间深度的约束，之后证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的深度不会改变有此定理保证，如此操作后问题的答案不会改变。,一个例子,A-1186643532103An因为35103，所以最小的k是3，我们先把35和32删除，得到他们的和67，并向前寻找一个第一个超过67的数，把67插入到他后面1866764103因为67103，所以k=2,67和64被删除了，和131应当放在186后186131103同上述操作，现在k=2（别忘了，还有A-1和An等于正无穷大）234186420最后的答案就是各次合并的重量之和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，