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

1、動(dòng)態(tài)規(guī)劃石子合并第1頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一信工2013020441問(wèn)題描述在一個(gè)圓形操場(chǎng)的四周擺放著n 堆石子,現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2 堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。 試設(shè)計(jì)一個(gè)算法，計(jì)算出將n堆石子合并成一堆的最小得分和最大得分。第2頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一此問(wèn)題的三個(gè)版本任意版：有N堆石子，現(xiàn)要將石子有序的合并成一堆，每次只能移動(dòng)任意的2堆石子合并，合并花費(fèi)為將的一堆石子的數(shù)量。(貪心算法，哈夫曼編碼問(wèn)題)直線版：在一條直線上擺著N堆石子，其余條件不變。圓形版：

2、石子是排成圓形，其余條件不變。第3頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一問(wèn)題初步分析如果N1次合并的全局最優(yōu)解包含了每一次合并的子問(wèn)題的最優(yōu)解，那么經(jīng)這樣的N1次合并后的得分總和必然是最優(yōu)的。此我們需要通過(guò)動(dòng)態(tài)規(guī)劃算法來(lái)求出最優(yōu)解。信工2013020441第4頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一信工2013020441問(wèn)題具體分析設(shè)m(i,j)定義為第i堆石子到第j堆石子合并后的最少總分?jǐn)?shù)。a(i)為第i堆石子得石子數(shù)量。當(dāng)合并的石子堆為1堆時(shí)，很明顯m(i,i)的分?jǐn)?shù)為0;當(dāng)合并的石子堆為2堆時(shí)，m(i,i+1)的分?jǐn)?shù)為a(i)+a(i+1); 當(dāng)合

3、并的石子堆為3堆時(shí)，m(i,i+2)的分?jǐn)?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); 當(dāng)合并的石子堆為4堆時(shí).第5頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一 動(dòng)態(tài)規(guī)劃通項(xiàng)通項(xiàng)式 aij = mink | aik + ak+1j + sumi.j, k = i.j-1（？）其中aij表示從第i堆到第j堆合并能夠取到的最小值，將其分解為兩部分，從i到k，以及從k+1到j(luò)，再加上兩大堆合并的得分。第6頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一部分關(guān)鍵代碼1int MatrixCh

4、ain_min(int pN,int n) /定義二維數(shù)組mij來(lái)記錄i到j(luò)的合并過(guò)成中最少石子數(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=0;/主對(duì)角線 for(int i=1;i=n-1;i+) int j=i+1; mij=pi+pj; 第7頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一 for(int r=3; r=n;r+) for(int i=1;i=n-r+1;i+) int j = i+r-1

5、; 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;第8頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一部分關(guān)鍵代碼2int main()int stoneN;min= MatrixChain_min(stone,n);max= MatrixChain_max(stone,

6、n);/將前面簡(jiǎn)化的問(wèn)題重新考慮進(jìn)來(lái)，將圓轉(zhuǎn)化為n個(gè)線性序列 for(int j=1;j=n-1;j+) int min_cache=0; int max_cache=0; int cache= stone1; for(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頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一程序運(yùn)行結(jié)果

7、第10頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一復(fù)雜度分析線性時(shí)為O(n2),環(huán)形時(shí)為O(n3)DP優(yōu)化重構(gòu)DP第11頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一優(yōu)化方案1DP優(yōu)化GarsiaWachs算法可以把時(shí)間復(fù)雜度壓縮到O(nlogn)The Art of Computer Programming第3卷6.2.2節(jié)概要：設(shè)一個(gè)序列是A0.n-1，每次尋找最小的一個(gè)滿足Ak-1Ak+Ak-1的j,把合并后的值A(chǔ)k+Ak-1插入Aj的后面。基本思想是通過(guò)樹的最優(yōu)性得到一個(gè)節(jié)點(diǎn)間深度的約束，之后證明操作一次之后的解可以和原來(lái)的解一一對(duì)應(yīng)，并保證節(jié)點(diǎn)移動(dòng)之后他所在

8、的深度不會(huì)改變有此定理保證，如此操作后問(wèn)題的答案不會(huì)改變。第12頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一一個(gè)例子A-1 186 64 35 32 103 An因?yàn)?5103，所以最小的k是3，我們先把35和32刪除，得到他們的和67，并向前尋找一個(gè)第一個(gè)超過(guò)67的數(shù)，把67插入到他后面186 67 64 103 因?yàn)?7103，所以k=2,67和64被刪除了，和131應(yīng)當(dāng)放在186后186 131 103同上述操作，現(xiàn)在k=2（別忘了，還有A-1和An等于正無(wú)窮大）234 186420最后的答案就是各次合并的重量之和420+234+131+67=852。第13頁(yè)，共16頁(yè)，2

9、022年，5月20日，15點(diǎn)19分，星期一優(yōu)化方案2重構(gòu)DP以(i，j)表示一個(gè)從第i堆數(shù)起，順時(shí)針數(shù)j堆時(shí)的子序列(雙參數(shù)DP，O(n2) 最佳合并方案包括兩個(gè)信息： 在該子序列的各堆石子合并成一堆的過(guò)程中，各次合并得分的總和 形成最佳得分和的子序列和子序列。由于兩個(gè)子序列是相鄰的， 因此只需記住子序列的堆數(shù) 設(shè): f(i，j)將子序列(i，j)中的j堆石子合并成一堆的最佳得分和 c(i，j)將(i，j)一分為二，其中子序列的堆數(shù) (iN，jN)第14頁(yè)，共16頁(yè)，2022年，5月20日，15點(diǎn)19分，星期一 fi， ci， （iN）f，f，fN，(sum(i,i+1)c，c，cN， (1)f，N，f，N，fN，Nc，N，c，N，cN，Nfi，jminfi，k