《动态规划石子合并PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《动态规划石子合并PPT讲稿.ppt（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态规划石子合并划石子合并第1页，共16页，编辑于2022年，星期五信工信工20130204412013020441问题描述问题描述u在一个圆形操场的四周摆放着在一个圆形操场的四周摆放着n 堆石子堆石子,现要将石子有现要将石子有次序地合并成一堆。次序地合并成一堆。u规定每次只能选相邻的规定每次只能选相邻的2 堆石子合并成新的一堆，并堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。将新的一堆石子数记为该次合并的得分。u试设计一个算法，计算出将试设计一个算法，计算出将n堆石子合并成一堆的最小得分和堆石子合并成一堆的最小得分和最大得分。最大得分。第2页，共16页，编辑于2022年，星期五
2、此问题的三个版本此问题的三个版本u任意版：有任意版：有N堆石子，现要将石子有序的合并成一堆，每次堆石子，现要将石子有序的合并成一堆，每次只能移动任意的只能移动任意的2堆石子合并，合并花费为将的一堆石子的数量。堆石子合并，合并花费为将的一堆石子的数量。(贪心算法，哈夫曼编码问题贪心算法，哈夫曼编码问题)u直线版：在一条直线上摆着直线版：在一条直线上摆着N堆石子，其余条件不变。堆石子，其余条件不变。u圆形版：石子是排成圆形，其余条件不变。圆形版：石子是排成圆形，其余条件不变。第3页，共16页，编辑于2022年，星期五问题初步分析问题初步分析u如果如果N1次合并的全局最优解包含了每一次合并次合并的全
3、局最优解包含了每一次合并的子问题的最优解，那么经这样的的子问题的最优解，那么经这样的N1次合并后次合并后的得分总和必然是最优的。的得分总和必然是最优的。u此我们需要通过动态规划算法来求出最优解。此我们需要通过动态规划算法来求出最优解。信工信工20130204412013020441第4页，共16页，编辑于2022年，星期五信工信工20130204412013020441问题具体分析问题具体分析设设m(i,j)定义为第定义为第i堆石子到第堆石子到第j堆石子合并后的最少总分堆石子合并后的最少总分数。数。a(i)为第为第i堆石子得石子数量。堆石子得石子数量。u当合并的石子堆为当合并的石子堆为1堆时，
4、很明显堆时，很明显m(i,i)的分数为的分数为0;u当合并的石子堆为当合并的石子堆为2堆时，堆时，m(i,i+1)的分数为的分数为a(i)+a(i+1);u当合并的石子堆为当合并的石子堆为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);u当合并的石子堆为当合并的石子堆为4堆时堆时.第5页，共16页，编辑于2022年，星期五 动态规划通项动态规划通项u通项式通项式 aij=mink|aik+ak+1j+sumi.j,k=i.j-1（？）（？）其中其中aij表示从第表示从
5、第i堆到第堆到第j堆合并能够取到的最小值，将其分堆合并能够取到的最小值，将其分解为两部分，从解为两部分，从i到到k，以及从，以及从k+1到到j，再加上两大堆合并的得分。，再加上两大堆合并的得分。第6页，共16页，编辑于2022年，星期五部分关键代码部分关键代码1int 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;
6、for(int g=1;g=n;g+)mgg=0;/主对角线主对角线 for(int i=1;i=n-1;i+)int j=i+1;mij=pi+pj;第7页，共16页，编辑于2022年，星期五 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=m
7、ik+mk+1j+sum;if(tmij)mij=t;/最终得到最优解最终得到最优解 min=m1n;return min;第8页，共16页，编辑于2022年，星期五部分关键代码部分关键代码2int main()int stoneN;min=MatrixChain_min(stone,n);max=MatrixChain_max(stone,n);/将前面简化的问题重新考虑进来，将圆转化为将前面简化的问题重新考虑进来，将圆转化为n个线性序列个线性序列 for(int j=1;j=n-1;j+)int min_cache=0;int max_cache=0;int cache=stone1;fo
8、r(int k=2;k=n;k+)stonek-1=stonek;stonen=cache;min_cache=MatrixChain_min(stone,n);max_cache=MatrixChain_max(stone,n);if(min_cachemax)max=max_cache;第9页，共16页，编辑于2022年，星期五程序运行结果程序运行结果第10页，共16页，编辑于2022年，星期五复杂度分析复杂度分析u线性时为线性时为O(n2),环形时为环形时为O(n3)uDP优化优化u重构重构DP第11页，共16页，编辑于2022年，星期五优化方案优化方案1uDP优化优化GarsiaWac
9、hs算法可以把时间复杂度压缩到算法可以把时间复杂度压缩到O(nlogn)The Art of Computer Programming第第3卷卷6.2.2节节概要：设一个序列是概要：设一个序列是A0.n-1，每次寻找最小的一个满足，每次寻找最小的一个满足Ak-1Ak+Ak-1的的j,把合并后的值把合并后的值Ak+Ak-1插入插入Aj的后面。的后面。基本思想是通过树的最优性得到一个节点间深度的约束，之后证基本思想是通过树的最优性得到一个节点间深度的约束，之后证明操作一次之后的解可以和原来的解一一对应，并保证节点移动明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的深度不会改变之
10、后他所在的深度不会改变有此定理保证，如此操作后问题的答案不会改变。有此定理保证，如此操作后问题的答案不会改变。第12页，共16页，编辑于2022年，星期五一个例子一个例子uA-1 186 64 35 32 103 An因为因为35103，所以最小的，所以最小的k是是3，我们先把，我们先把35和和32删除，得到删除，得到他们的和他们的和67，并向前寻找一个第一个超过，并向前寻找一个第一个超过67的数，把的数，把67插入到插入到他后面他后面u186 67 64 103 因为因为67103，所以，所以k=2,67和和64被删除了，和被删除了，和131应当放在应当放在186后后u186 131 103
11、同上述操作，现在同上述操作，现在k=2（别忘了，还有（别忘了，还有A-1和和An等于正无等于正无穷大）穷大）u234 186u420u最后的答案就是各次合并的重量之和最后的答案就是各次合并的重量之和420+234+131+67=852。第13页，共16页，编辑于2022年，星期五优化方案优化方案2u重构重构DP以以(i，j)表示一个从第表示一个从第i堆数起，顺时针数堆数起，顺时针数j堆时的子序列堆时的子序列(双参数双参数DP，O(n2)最佳合并方案包括两个信息：最佳合并方案包括两个信息：在该子序列的各堆石子合并成一堆的过程中，各次合并得分的在该子序列的各堆石子合并成一堆的过程中，各次合并得分的
12、总和总和 形成最佳得分和的子序列和子序列。由于两个子序列是相形成最佳得分和的子序列和子序列。由于两个子序列是相邻的，邻的，因此只需记住子序列的堆数因此只需记住子序列的堆数 设设:f(i，j)将子序列将子序列(i，j)中的中的j堆石子合并成一堆的最佳得分和堆石子合并成一堆的最佳得分和 c(i，j)将将(i，j)一分为二，其中子序列的堆数一分为二，其中子序列的堆数 (iN，jN)第14页，共16页，编辑于2022年，星期五u fi，u ci，（iN）uf，f，fN，(sum(i,i+1)uc，c，cN，(1)uf，N，f，N，fN，Nuc，N，c，N，cN，Nfi，jminfi，kfx，jksumkjci，jk fi，jfi，kfx，j-ksum（，）u其中其中x（ik）mod n，即第，即第i堆数起，顺时针数堆数起，顺时针数 k堆的堆序号堆的堆序号第15页，共16页，编辑于2022年，星期五Thank you!第16页，共16页，编辑于2022年，星期五