動態(tài)規(guī)劃石子合并

動態(tài)規(guī)劃石子合并第1頁，課件共16頁，創(chuàng)作于2023年2月信工2013020441問題描述在一個圓形操場的四周擺放著n堆石子,現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。

試設(shè)計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分。第2頁，課件共16頁，創(chuàng)作于2023年2月此問題的三個版本任意版：有N堆石子，現(xiàn)要將石子有序的合并成一堆，每次只能移動任意的2堆石子合并，合并花費為將的一堆石子的數(shù)量。 (貪心算法，哈夫曼編碼問題)直線版：在一條直線上擺著N堆石子，其余條件不變。圓形版：石子是排成圓形，其余條件不變。第3頁，課件共16頁，創(chuàng)作于2023年2月問題初步分析如果N－1次合并的全局最優(yōu)解包含了每一次合并的子問題的最優(yōu)解，那么經(jīng)這樣的N－1次合并后的得分總和必然是最優(yōu)的。此我們需要通過動態(tài)規(guī)劃算法來求出最優(yōu)解。信工2013020441第4頁，課件共16頁，創(chuàng)作于2023年2月信工2013020441問題具體分析

設(shè)m(i,j)定義為第i堆石子到第j堆石子合并后的最少總分數(shù)。a(i)為第i堆石子得石子數(shù)量。當合并的石子堆為1堆時，很明顯m(i,i)的分數(shù)為0;當合并的石子堆為2堆時，m(i,i+1)的分數(shù)為a(i)+a(i+1);

當合并的石子堆為3堆時，m(i,i+2)的分數(shù)為

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堆時......第5頁，課件共16頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃通項通項式 a[i][j]=min{k|a[i][k]+a[k+1][j]+sum[i...j],k=i...j-1} （？） 其中a[i][j]表示從第i堆到第j堆合并能夠取到的最小值，將其分解為兩部分，從i到k，以及從k+1到j(luò)，再加上兩大堆合并的得分。第6頁，課件共16頁，創(chuàng)作于2023年2月部分關(guān)鍵代碼1intMatrixChain_min(intp[N],intn){//定義二維數(shù)組m[i][j]來記錄i到j(luò)的合并過成中最少石子數(shù)目

//此處賦值為-1

intm[N][N]; //初始化

for(intx=1;x<=n;x++)for(intz=1;z<=n;z++){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];}第7頁，課件共16頁，創(chuàng)作于2023年2月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<j;k++){intt=m[i][k]+m[k+1][j]+sum;if(t<m[i][j])m[i][j]=t;}}//最終得到最優(yōu)解

min=m[1][n];returnmin;}第8頁，課件共16頁，創(chuàng)作于2023年2月部分關(guān)鍵代碼2intmain(){intstone[N];···min=MatrixChain_min(stone,n);max=MatrixChain_max(stone,n);//將前面簡化的問題重新考慮進來，將圓轉(zhuǎn)化為n個線性序列

for(intj=1;j<=n-1;j++){intmin_cache=0;intmax_cache=0;intcache=stone[1];for(intk=2;k<=n;k++){stone[k-1]=stone[k];}stone[n]=cache;min_cache=MatrixChain_min(stone,n);max_cache=MatrixChain_max(stone,n);if(min_cache<min)min=min_cache;if(max_cache>max)max=max_cache;}···}第9頁，課件共16頁，創(chuàng)作于2023年2月程序運行結(jié)果第10頁，課件共16頁，創(chuàng)作于2023年2月復雜度分析線性時為O(n^2),環(huán)形時為O(n^3)DP優(yōu)化重構(gòu)DP第11頁，課件共16頁，創(chuàng)作于2023年2月優(yōu)化方案1DP優(yōu)化 GarsiaWachs算法可以把時間復雜度壓縮到O(nlogn) 《TheArtofComputerProgramming》第3卷6.2.2節(jié) 概要：設(shè)一個序列是A[0..n-1]，每次尋找最小的一個滿足A[k-1]<=A[k+1]的k，(方便起見設(shè)A[-1]和A[n]等于正無窮大) 那么我們就把A[k]與A[k-1]合并，之后找最大的一個滿足A[j]>A[k]+A[k-1]的j,把合并后的值A(chǔ)[k]+A[k-1]插入A[j]的后面。 基本思想是通過樹的最優(yōu)性得到一個節(jié)點間深度的約束，之后證明操作一次之后的解可以和原來的解一一對應(yīng)，并保證節(jié)點移動之后他所在的深度不會改變 有此定理保證，如此操作后問題的答案不會改變。第12頁，課件共16頁，創(chuàng)作于2023年2月一個例子A[-1]186

64

35

32

103A[n] 因為35<103，所以最小的k是3，我們先把35和32刪除，得到他們的和67，并向前尋找一個第一個超過67的數(shù)，把67插入到他后面186

67

64

103 因為67<103，所以k=2,67和64被刪除了，和131應(yīng)當放在186后186

131

103 同上述操作，現(xiàn)在k=2（別忘了，還有A[-1]和A[n]等于正無窮大）234186420最后的答案就是各次合并的重量之和

420+234+131+67=852。第13頁，課件共16頁，創(chuàng)作于2023年2月優(yōu)化方案2重構(gòu)DP

以(i，j)表示一個從第i堆數(shù)起，順時針數(shù)j堆時的子序列 (雙參數(shù)DP，O(n^2)) 最佳合并方案包括兩個信息：①在該子序列的各堆石子合并成一堆的過程中，各次合并得分的總和②形成最佳得分和的子序列１和子序列２。由于兩個子序列是相鄰的，因此只需記住子序列１的堆數(shù)設(shè):f(i，j)──將子序列(i，j)中的j堆石子合并成一堆的最佳得分和c(i，j)──將(i，j)一分為二，其中子序列１的堆數(shù)(１≤i≤N，１≤j≤N)第14頁，課件共16頁，創(chuàng)作于2023年2月f〔i，１〕＝０

c〔i，１〕＝０（１≤i≤N）f〔１，２〕，f〔２，２〕，……，f〔N，２〕(sum(i,i+1))c〔１，２〕，c〔２，２〕，……，c〔N，２〕(1) ……f〔１，N〕，f〔２，N〕，……，f〔N，N〕c〔１，N〕，c〔２，N〕，……，c〔N，N〕f〔i，j〕＝min｛f〔i，k〕＋f〔x，j