1、動態(tài)規(guī)劃思想：石子合并問題,信工2013020441,問題描述,在一個圓形操場的四周擺放著n 堆石子,現(xiàn)要將石子有次序地合并成一堆。 規(guī)定每次只能選相鄰的2 堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。 試設(shè)計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分。,此問題的三個版本,任意版：有N堆石子，現(xiàn)要將石子有序的合并成一堆，每次只能移動任意的2堆石子合并，合并花費為將的一堆石子的數(shù)量。 (貪心算法，哈夫曼編碼問題) 直線版：在一條直線上擺著N堆石子，其余條件不變。 圓形版：石子是排成圓形，其余條件不變。,問題初步分析,如果N1次合并的全局最優(yōu)解包含了每一次合并的子問題

2、的最優(yōu)解，那么經(jīng)這樣的N1次合并后的得分總和必然是最優(yōu)的。 此我們需要通過動態(tài)規(guī)劃算法來求出最優(yōu)解。,信工2013020441,信工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堆時.

3、,動態(tài)規(guī)劃通項,通項式 aij = mink | aik + ak+1j + sumi.j, k = i.j-1（？） 其中aij表示從第i堆到第j堆合并能夠取到的最小值，將其分解為兩部分，從i到k，以及從k+1到j(luò)，再加上兩大堆合并的得分。,部分關(guān)鍵代碼1,int MatrixChain_min(int pN,int n) /定義二維數(shù)組mij來記錄i到j(luò)的合并過成中最少石子數(shù)目 /此處賦值為-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=

4、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; /最終得到最優(yōu)解 min=m1n; return min; ,部分關(guān)

5、鍵代碼2,int main() int stoneN; min= MatrixChain_min(stone,n); max= MatrixChain_max(stone,n); /將前面簡化的問題重新考慮進來，將圓轉(zhuǎn)化為n個線性序列 for(int j=1;jmax) max=max_cache; ,程序運行結(jié)果,復(fù)雜度分析,線性時為O(n2),環(huán)形時為O(n3) DP優(yōu)化 重構(gòu)DP,優(yōu)化方案1,DP優(yōu)化 GarsiaWachs算法可以把時間復(fù)雜度壓縮到O(nlogn) The Art of Computer Programming第3卷6.2.2節(jié) 概要：設(shè)一個序列是A0.n-1，每次尋找

6、最小的一個滿足Ak-1Ak+Ak-1的j,把合并后的值A(chǔ)k+Ak-1插入Aj的后面。 基本思想是通過樹的最優(yōu)性得到一個節(jié)點間深度的約束，之后證明操作一次之后的解可以和原來的解一一對應(yīng)，并保證節(jié)點移動之后他所在的深度不會改變 有此定理保證，如此操作后問題的答案不會改變。,一個例子,A-1 186 64 35 32 103 An 因為35103，所以最小的k是3，我們先把35和32刪除，得到他們的和67，并向前尋找一個第一個超過67的數(shù)，把67插入到他后面 186 67 64 103 因為67103，所以k=2,67和64被刪除了，和131應(yīng)當放在186后 186 131 103 同上述操作，現(xiàn)在

7、k=2（別忘了，還有A-1和An等于正無窮大） 234 186 420 最后的答案就是各次合并的重量之和 420+234+131+67=852。,優(yōu)化方案2,重構(gòu)DP 以(i，j)表示一個從第i堆數(shù)起，順時針數(shù)j堆時的子序列 (雙參數(shù)DP，O(n2) 最佳合并方案包括兩個信息： 在該子序列的各堆石子合并成一堆的過程中，各次合并得分的總和 形成最佳得分和的子序列和子序列。由于兩個子序列是相鄰的， 因此只需記住子序列的堆數(shù) 設(shè): f(i，j)將子序列(i，j)中的j堆石子合并成一堆的最佳得分和 c(i，j)將(i，j)一分為二，其中子序列的堆數(shù) (iN，jN),fi， ci， （iN） f，f，fN，(sum(i,i+1) c，c，cN， (1) f，N，f，N，fN