雙向廣度搜索詳解

1、1.1 廣度雙向搜索的概念所謂雙向搜索指的是搜索沿兩個(gè)力向同時(shí)進(jìn)行：正向搜索：從初始結(jié)點(diǎn)向目標(biāo)結(jié)點(diǎn)方向搜索；逆向搜索：從目標(biāo)結(jié)點(diǎn)向初始結(jié)點(diǎn)方向搜索；當(dāng)兩個(gè)方向的搜索生成同一子結(jié)點(diǎn)時(shí)終止此搜索過程。1. 2 廣度雙向搜索算法廣度雙向搜索通常有兩中方法：1. 兩個(gè)方向交替擴(kuò)展2. 選擇結(jié)點(diǎn)個(gè)數(shù)較少的那個(gè)力向先擴(kuò)展方法2克服了兩方向結(jié)點(diǎn)的生成速度不平衡的狀態(tài)，明顯提高了效率。算法說明：設(shè)置兩個(gè)隊(duì)列c:array0.1,1.maxn of jid，分別表示正向和逆向的擴(kuò)展隊(duì)列。設(shè)置兩個(gè)頭指針head:array0.1 of integer 分別表示正向和逆向當(dāng)前將擴(kuò)展結(jié)點(diǎn)的頭指針。 設(shè)置兩個(gè)尾指針ta

2、il:array0.1 of integer 分別表示正向和逆向的尾指針。maxn表示隊(duì)列最大長度。算法描述如下：1.主程序代碼repeat選擇節(jié)點(diǎn)數(shù)較少且隊(duì)列未空、未滿的方向先擴(kuò)展if (tail0<=tail1) and not(head0>=tail0)or(tail0>=maxn) then expand(0); if (tail1<=tail0) and not(head1>=tail1)or(tail1>=maxn) then expand(1); 如果一方搜索終止，繼續(xù)另一方的搜索，直到兩個(gè)方向都終止if not(head0>=tail0

3、)or(tail0>=maxn) then expand(0);if not(head1>=tail1)or(tail1>=maxn) then expand(1);Until (head0>=tail0)or(tail0>=maxn) And (head1>=tail1)or(tail1>=maxn)2.expand(st:0.1)程序代碼如下:inc(headst;取出隊(duì)列當(dāng)前待擴(kuò)展的結(jié)點(diǎn)cst,headstfor i:=1 to maxk dobeginif tailst>=maxn then exit;inc(tailst);產(chǎn)生新結(jié)點(diǎn);

4、check(st);檢查新節(jié)點(diǎn)是否重復(fù)end;3.check(st:0.1)程序代碼:for i:=1 to tailst-1 doif cst,tailst.*=cst,i.* then begin dec(tailst);exit end;bool(st);如果節(jié)點(diǎn)不重復(fù)，再判斷是否到達(dá)目標(biāo)狀態(tài)4.bool(st:0.1)程序代碼:for i:=1 to tail1-st doif cst,tailst.*=c1-st,i.* then print(st,tailst,i);如果雙向搜索相遇（即得到同一節(jié)點(diǎn)），則輸出結(jié)果5.print(st,tail,k)程序代碼：if st=0 then

5、 begin print0(tail);print1(k) end;else begin print0(k);print1(tail) end;6.print0(m)程序代碼：if m<>0 then begin print(c0,m.f);輸出c0,m.* end;輸出正方向上產(chǎn)生的結(jié)點(diǎn)7.print1(m)程序代碼;n:=c1,m.fwhile m<>0begin輸出c1,n.*;n:=c1,n.f;end輸出反方向上產(chǎn)生的結(jié)點(diǎn)1.3 例題與習(xí)題例1：8數(shù)碼難題 ：2 8 3 1 2 31 6 4 -> 8 4（用最少的步數(shù)）7 5 7 6 5程序如下：pro

6、gram num8;const maxn=4000;type jid=recordstr:string9;f:0.maxn;dep:byte;end;bin=0.1;var c:array0.1,1.maxn of jid;head,tail:array0.1 of integer;start,goal:string9;procedure init;var i,j:integer;beginstart:='283164705'goal:='123804765'for i:=0 to 1 dofor j:=1 to maxn donew(ci,j);c0,1.st

7、r:=start; c0,1.f:=0; c0,1.dep:=0;c1,1.str:=goal; c1,1.f:=0; c1,1.dep:=0;for i:=0 to 1 dobegin headi:=0;taili:=1;end;end;procedure print(st:bin;tail,k:integer);procedure print0(m:integer);beginif m<>0 thenbegin print0(c0,m.f);writeln(c0,m.str) end;end;procedure print1(m:integer);var n:integer;b

8、eginn:=c1,m.f;while n<>0 dobegin writeln(c1,n.str); n:=c1,n.f end;end;beginif st=0 thenbegin writeln('step=',c0,tail.dep+c1,k.dep);print0(tail); print1(k);endelse begin writeln('step=',c0,k.dep+c1,tail.dep);print0(k); print1(tail); end ;halt;end;procedure check(st:bin);procedur

9、e bool(st:bin);var i:integer;beginfor i:=1 to tail1-st doif cst,tailst.str=c1-st,i.str then print(st,tailst,i);end;var i:integer;beginfor i:=1 to tailst-1 doif cst,tailst.str=cst,i.str thenbegin dec(tailst);exit end;bool(st);end;procedure expand(st:bin);var i,p0,p1,d:integer;str0,str1:string9;begini

10、nc(headst);str0:=cst,headst.str;d:=cst,headst.dep;p0:=pos('0',str0);for i:=1 to 4 dobeginif tailst>=maxn then exit;p1:=p0+2*i-5;if (p1 in 1.9) and not (p0=3) and (p1=4)and not(p0=4)and (p1=3) and not(p0=6)and(p1=7)and not(p0=7)and(p1=6)thenbegininc(tailst);str1:=str0;str1p0:=str1p1;str1p1

11、:='0'cst,tailst.str:=str1;cst,tailst.f:=headst;cst,tailst.dep:=d+1;check(st);end;end;end;begininit;check(0);repeatif (tail0<=tail1) and not(head0>=tail0)or(tail0>=maxn)then expand(0);if (tail1<=tail0) and not(head1>=tail1)or(tail1>=maxn)then expand(1);if not(head0>=tail0

12、)or(tail0>=maxn) then expand(0);if not(head1>=tail1)or(tail1>=maxn) then expand(1);Until(head0>=tail0)or(tail0>=maxn)And(head1>=tail1)or(tail1>=maxn); writeln('No answer');end.動態(tài)規(guī)劃總結(jié)專題一 狀態(tài)表示在用動態(tài)規(guī)劃解題時(shí)，我么往往第一個(gè)考慮的是數(shù)組維數(shù)，其實(shí)數(shù)組維度（和狀態(tài)表示）是有規(guī)律可循的：A. 二維空間的DP：一般采用二位數(shù)組di，j表示當(dāng)i，j為某一邊角

13、時(shí)的極值（e：di，j可以表示以i，j為右上角時(shí)所能構(gòu)成的正方形的邊長最大值聽不懂？接著往下看）。這種表示解決“多次訪問同一圖”類的DP題很有用。 階段決策類的DP：這里指階段劃分十分明顯的題（0/1背包）。一般采用di,j表示執(zhí)行到第i各階段，剩余代價(jià)為j時(shí)，所能取得的最高分。（如果限制條件多，可增加維度）。 樹形關(guān)系類的DP：一般用di來表示以i為根節(jié)點(diǎn)的最優(yōu)值，可以加維來保證正確性。 線性關(guān)系類的DP：這一類的DP最簡單，是每一個(gè)OIER的必備基礎(chǔ)，在這里就不廢話了。 專題二 狀態(tài)轉(zhuǎn)移（專題二與專題一的分類標(biāo)準(zhǔn)不同，因?yàn)閐ugushuiyi說這樣分更好，感謝他） 線性轉(zhuǎn)移一般公式：di=

14、 operation（dj+wj，i）（wi為由j轉(zhuǎn)移到i的消耗）operation為求最值 階段性轉(zhuǎn)移 一般公式：di，j：= operation（di-1，k+wk，j，di-2，）如果只涉及到前面的有限個(gè)階段，可以使用滾動數(shù)組。DI mod n，j= operation（d(i-1)mod n，k+wk，j，d(i-2)mod n，） 樹性轉(zhuǎn)移 一般公式：Di，j=max（dlsoni，k1+wj，k1，drsoni，k2+wj，k2） 遍歷順序一般為后序遍歷順序。 多維空間轉(zhuǎn)移 一般公式：di，j:=max(di-1,j+w1,di,j-1+w2) 復(fù)雜度分析：DP的復(fù)雜度為:狀態(tài)表示

15、的數(shù)組維數(shù)*狀態(tài)轉(zhuǎn)移的代價(jià)So A 的復(fù)雜度為O（n2）BCD:O(n3);專題三 題目分類總結(jié)一般類試題題庫：最長不下降子序列最長匹配前綴郵票組合共性總結(jié)：題目一般可以通過for 語句來枚舉狀態(tài)，所以時(shí)間復(fù)雜度為O（N2）本類的狀態(tài)是基礎(chǔ)的基礎(chǔ)，大部分的動態(tài)規(guī)劃都要用到它，成為一個(gè)維。一般來說，有兩種編號的狀態(tài)：狀態(tài)(i)表示前i個(gè)元素決策組成的一個(gè)狀態(tài)。狀態(tài)(i)表示用到了第i個(gè)元素，和其他在1到i-1間的元素，決策組成有的一個(gè)狀態(tài)。01背包：（重點(diǎn)）題庫：01背包（USACO、vijos1025、1104）裝箱問題（NOIP01 Trade 4）、取火柴問題(sgu153 Playing

16、 with matches)共性總結(jié)：一般都從階段的角度來表示狀態(tài)因?yàn)閐i，j只與di-1，k有關(guān)，所以可以用滾動數(shù)組來實(shí)現(xiàn)。Dodd（i），j各例分析：采藥（NOIP2006、vijos）一個(gè)背包，每個(gè)物品只能放一次。(1)Di，j：=max（di，j，di，j-ti+pi）；DI,j表示決策了前i個(gè)物品，花費(fèi)了j的代價(jià)優(yōu)化：滾動數(shù)組.(2)Dodd（i），j：=max（di-1，j，dodd（i-1），j-ti+pi）；觀察(2)不難發(fā)現(xiàn)，當(dāng)我們算到j(luò)時(shí)，1j-1并沒有更新，而di-1，j-ti一定在1j-1的范圍內(nèi)，所以完全可以用一位數(shù)組，方程為：di：=max（di，di-tj+pj）

17、在最外層循環(huán)一下j就ok了。（精益求精）總分（USACO）一個(gè)背包，可以重復(fù)放物品。Di：=max（di，di-tj+pj）Di表示花費(fèi)i各單位時(shí)間所能達(dá)到的最大值。（較簡單）Raucous Rockers（USACO）多個(gè)背包，不可以重復(fù)放物品，但放物品的順序有限制。dI,j,k:=max(dI-1,j,k,dI-1,j,k-ti+pi,di-1,j-1,maxtime-ti)dI,j,k表示決策到第i個(gè)物品、第j個(gè)背包，此背包花費(fèi)了k的空間。dI-1,j,k表示不取i，dI-1,j,k-ti表示取了i病房入背包j中，di-1,j-1,maxtime-ti 表示取了i病房入背包j-1中。比較

18、好理解。（本題也可以用滾動數(shù)組優(yōu)化）Fence Rails（USACO）多個(gè)背包，不可以重復(fù)放物品，但放物品的順序無限制。這道題只能用search做了，因?yàn)榉盼锲返捻樞驘o限制，無論怎么表示狀態(tài)，都不能保證無后效性。 4（為什么1 、2題可以？想一想。因?yàn)橹挥幸粋€(gè)背包）背包為題的版本還有很多，但萬變不離其宗，我們應(yīng)該拋開背景，來觀察問題的實(shí)質(zhì)。小錦言：我也做過和1、2、3類似的背包問題，有些版本和1、2、3極像，但不能使用DP，因?yàn)樗鼘⒁恍┍举|(zhì)的條件更改了。 旅游DP：題庫：方格取數(shù)(NOIP00 advance 4)旅行商簡化版（VIJOS）（歐幾里德回路） 巡游加拿大（IOI95、USACO

19、） 三取方格數(shù)（VIJOS） Hill（VIJOS）花店櫥窗布置(IOI99) 共性分析：1、行走方向決定階段性有規(guī)定源點(diǎn)與終點(diǎn)。每次行走方向都有一定的規(guī)定，使原點(diǎn)到終點(diǎn)的所有路徑形成無環(huán)有向圖。 2、決策稀疏性 就是所謂走法，若對于一個(gè)狀態(tài)，它的前驅(qū)或者后繼數(shù)很少(從無環(huán)有向圖角度，就是入度或出度少)，稱決策稀疏。 3、狀態(tài)稀疏性就是很多狀態(tài)是沒有用的，如排列的LCS,狀態(tài)為2維的(x,y)，但對于一個(gè)x只有一個(gè)y是有效個(gè)。所以實(shí)質(zhì)上狀態(tài)數(shù)還是線形的。 4 、 階段劃分不明顯 （1、2、3 by Amber） 各例分析： 一取方格數(shù)m*n的方格內(nèi)填上一些數(shù)，從1，1出發(fā)，只能向上或向右走，

20、走到m，n使得所經(jīng)方格的數(shù)字之和最大。題目很簡單，不說了。三取方格數(shù)與上題類似，要求走三遍（可以重復(fù)），使得三遍所經(jīng)方格的數(shù)字之和最大。dnum,i,j,k:=max(dnum-1,i-1,j,k, dnum-1,i-1,j-1,kdnum-1,i-1,j-1,k-1, dnum-1,i-1,j,k-1 dnum-1,i,j,k, dnum-1,i-1,j-1,kdnum-1,i,j-1,k-1, dnum-1,i-1,j,k-1)dnum，i，j，k表示三個(gè)人在第num各階段，的i，j，k位置（i<=j<=k）是的最優(yōu)值。1、 巡游加拿大（IOI95、USACO）從東至西有m個(gè)城

21、市，其中某些城市之間有航班，讓你從最東邊的城市出發(fā)，坐航班每次只能向西走，走到最西邊之后再往回走到最東邊的城市（除了兩端的城市，其他城市只能經(jīng)過一次），使得經(jīng)過的城市數(shù)量盡可能多。（東至西至東=兩個(gè)人同時(shí)向西走且經(jīng)過的城市不相同）設(shè)di,j表示從起點(diǎn)出發(fā)，一個(gè)人到達(dá)i，另一個(gè)人到達(dá)j時(shí)經(jīng)過的城市數(shù)。因?yàn)閐i,j=dj,i，所以我們限制i>j。分析狀態(tài)(i,j)，它可能是(k,j)(j<k<i)中k到達(dá)i得到（方式1），也可能是(j,k)(k<j)中k超過j到達(dá)i得到（方式2）。但它不能是(i,k)(k<j)中k到達(dá)j得到，因?yàn)檫@樣可能會出現(xiàn)重復(fù)路徑。即使不會出現(xiàn)重

22、復(fù)路徑，那么它由(j,k)通過方式2同樣可以得到，所以不會遺漏解。所以狀態(tài)轉(zhuǎn)移方程是：di,j=maxdk,j+1(k,i可達(dá)且j<k<i),dj,k+1(k,i可達(dá)且k<j)。 時(shí)間復(fù)雜度O(n)（by forverstar）一、 環(huán)形DP：題庫： 數(shù)字游戲（VIJOS）HILL（VIJOS）看似很難，只要想清楚就可以了。二、 樹形DP：題庫： 加分二叉樹（NOI、VIJOS）選課（NOI、VIJOS）這兩道題網(wǎng)上的解題報(bào)告很多，我就不羅嗦了。其他練習(xí)題：a) 括號序列(Problem B, NEERC 2001)b) 多邊形(IOI98)c) 石子合并(NOI95 2)構(gòu)

23、造最優(yōu)二叉排序樹(CTSC96 2)a) 整數(shù)劃分常應(yīng)用在將一個(gè)權(quán)分配給一定的小分割塊，如：將大堆的石子分成一定的小堆，小堆可為空，大堆要分完。有時(shí)應(yīng)用在樹型動態(tài)規(guī)劃（二叉轉(zhuǎn)多叉）中。b) 乘積最大(NOIP00 Advance 2)推薦題庫：VIJOS動態(tài)規(guī)劃專題 3動態(tài)規(guī)劃算法的優(yōu)化技巧一、引言動態(tài)規(guī)劃是一種重要的程序設(shè)計(jì)方法，在信息學(xué)競賽中具有廣泛的應(yīng)用。使用動態(tài)規(guī)劃方法解題，對于不少問題具有空間耗費(fèi)大、時(shí)間效率高的特點(diǎn)，因此人們在研究動態(tài)規(guī)劃解題時(shí)更多的注意空間復(fù)雜度的優(yōu)化，運(yùn)用各種技巧將空間需求控制在軟硬件可以承受的范圍之內(nèi)。但是，也有一部分問題在使用動態(tài)規(guī)劃思想解題時(shí)，時(shí)間效率并不

24、能滿足要求，而且算法仍然存在優(yōu)化的余地，這時(shí)，就需要考慮時(shí)間效率的優(yōu)化。本文討論的是在確定使用動態(tài)規(guī)劃思想解題的情況下，對原有的動態(tài)規(guī)劃解法的優(yōu)化，以求降低算法的時(shí)間復(fù)雜度，使其能夠適用于更大的規(guī)模。二、動態(tài)規(guī)劃時(shí)間復(fù)雜度的分析使用動態(tài)規(guī)劃方法解題，對于不少問題之所以具有較高的時(shí)間效率，關(guān)鍵在于它減少了“冗余”。所謂“冗余”，就是指不必要的計(jì)算或重復(fù)計(jì)算部分，算法的冗余程度是決定算法效率的關(guān)鍵。動態(tài)規(guī)劃在將問題規(guī)模不斷縮小的同時(shí)，記錄已經(jīng)求解過的子問題的解，充分利用求解結(jié)果，避免了反復(fù)求解同一子問題的現(xiàn)象，從而減少了冗余。但是，動態(tài)規(guī)劃求解問題時(shí)，仍然存在冗余。它主要包括：求解無用的子問題，對

25、結(jié)果無意義的引用等等。 下面給出動態(tài)規(guī)劃時(shí)間復(fù)雜度的決定因素：時(shí)間復(fù)雜度=狀態(tài)總數(shù)*每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)*每次狀態(tài)轉(zhuǎn)移的時(shí)間1下文就將分別討論對這三個(gè)因素的優(yōu)化。這里需要指出的是：這三者之間不是相互獨(dú)立的，而是相互聯(lián)系，矛盾而統(tǒng)一的。有時(shí)，實(shí)現(xiàn)了某個(gè)因素的優(yōu)化，另外兩個(gè)因素也隨之得到了優(yōu)化；有時(shí)，實(shí)現(xiàn)某個(gè)因素的優(yōu)化卻要以增大另一因素為代價(jià)。因此，這就要求我們在優(yōu)化時(shí)，堅(jiān)持“全局觀”，實(shí)現(xiàn)三者的平衡。三、動態(tài)規(guī)劃時(shí)間效率的優(yōu)化3.1 減少狀態(tài)總數(shù)：我們知道，動態(tài)規(guī)劃的求解過程實(shí)際上就是計(jì)算所有狀態(tài)值的過程，因此狀態(tài)的規(guī)模直接影響到算法的時(shí)間效率。所以，減少狀態(tài)總數(shù)是動態(tài)規(guī)劃優(yōu)化的重要部分，本節(jié)將

26、討論減少狀態(tài)總數(shù)的一些方法。1、改進(jìn)狀態(tài)表示狀態(tài)的規(guī)模與狀態(tài)表示的方法密切相關(guān)，通過改進(jìn)狀態(tài)表示減小狀態(tài)總數(shù)是應(yīng)用較為普遍的一種方法。例一、 Raucous Rockers 演唱組（USACO96）問題描述現(xiàn)有n首由Raucous Rockers 演唱組錄制的珍貴的歌曲，計(jì)劃從中選擇一些歌曲來發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的標(biāo)準(zhǔn)進(jìn)行選擇：（1） 這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序；（2） 包含歌曲的總數(shù)盡可能多。輸入n，m，t，和n首歌曲的長度，它們按照創(chuàng)作順序排序，沒有一首歌超出一張唱片的長度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的

27、最多的歌曲數(shù)目。（1n, m, t20）算法分析本題要求唱片中的歌曲必須按照它們創(chuàng)作順序排序，這就滿足了動態(tài)規(guī)劃的無后效性要求，啟發(fā)我們采用動態(tài)規(guī)劃進(jìn)行解題。分析可知，該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，即：設(shè)最優(yōu)錄制方案中第i首歌錄制的位置是從第j張唱片的第k分鐘開始的，那么前j-1張唱片和第j張唱片的前k-1分鐘是前1.i-1首歌的最優(yōu)錄制方案，也就是說，問題的最優(yōu)解包含了子問題的最優(yōu)解。設(shè)n首歌曲按照寫作順序排序后的長度為long1.n，則動態(tài)規(guī)劃的狀態(tài)表示描述為： gi, j, k，0in，0jm，0k<t，表示前i首歌曲，用j張唱片另加k分鐘來錄制，最多可以錄制的歌曲數(shù)目，則問題的最優(yōu)解

28、為gn,m,0。由于歌曲i有發(fā)行和不發(fā)行兩種情況，而且還要分另加的k分鐘是否能錄制歌曲i。這樣我們可以得到如下的狀態(tài)轉(zhuǎn)移方程和邊界條件：當(dāng)klongi，i1時(shí)： gi, j, k=maxgi-1,j,k-longi，gi-1,j,k當(dāng)k<longi，i1時(shí)： gi, j, k=maxgi-1,j-1,t-longi，gi-1,j,k規(guī)劃的邊界條件為：當(dāng)0k<t時(shí)：g0,0,k=0;我們來分析上述算法的時(shí)間復(fù)雜度，上述算法的狀態(tài)總數(shù)為O(n*m*t)，每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(1)，每次狀態(tài)轉(zhuǎn)移的時(shí)間為O(1)，所以總的時(shí)間復(fù)雜度為O(n*m*t)。由于n，m，t均不超過20，所以可

29、以滿足要求。算法優(yōu)化當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，上述算法就無法滿足要求，我們來考慮通過改進(jìn)狀態(tài)表示提高算法的時(shí)間效率。本題的最優(yōu)目標(biāo)是用給定長度的若干張唱片錄制盡可能多的歌曲，這實(shí)際上等價(jià)于在錄制給定數(shù)量的歌曲時(shí)盡可能少地使用唱片。所謂“盡可能少地使用唱片”，就是指使用的完整的唱片數(shù)盡可能少，或是在使用的完整的唱片數(shù)相同的情況下，另加的分鐘數(shù)盡可能少。分析可知，在這樣的最優(yōu)目標(biāo)之下，該問題同樣具有最優(yōu)子結(jié)構(gòu)性質(zhì)，即：設(shè)D在前i首歌中選取j首歌錄制的最少唱片使用方案，那么若其中選取了第i首歌，則D-i是在前i-1首歌中選取j-1首歌錄制的最少唱片使用方案，否則D前i-1首歌中選取j首歌錄制的最少唱片使用方

30、案，同樣，問題的最優(yōu)解包含了子問題的最優(yōu)解。改進(jìn)的狀態(tài)表示描述為：gi, j=(a, b)，0in，0ji，0am，0bt，表示在前i首歌曲中選取j首錄制所需的最少唱片為：a張唱片另加b分鐘。由于第i首歌分為發(fā)行和不發(fā)行兩種情況，這樣我們可以得到如下的狀態(tài)轉(zhuǎn)移方程和邊界條件：gi, j=mingi-1,j，gi-1,j-1+longi其中(a, b)+longi=(a, b)的計(jì)算方法為：當(dāng)longit-b時(shí)： a=a; b=b+longi;當(dāng)longi>t-b時(shí)： a=a+1; b=longi;規(guī)劃的邊界條件： gi,0=(0,0) 0in這樣題目所求的最大值是：ans=maxk| g

31、n, k(m-1,t)改進(jìn)后的算法，狀態(tài)總數(shù)為O(n2)，每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(1)，每次狀態(tài)轉(zhuǎn)移的時(shí)間為O(1)，所以總的時(shí)間復(fù)雜度為O(n2)。值得注意的是，算法的空間復(fù)雜度也由改進(jìn)前的O(m*n*t)降至優(yōu)化后的O(n2)。（程序及優(yōu)化前后的運(yùn)行結(jié)果比較見附件）通過對本題的優(yōu)化，我們認(rèn)識到：應(yīng)用不同的狀態(tài)表示方法設(shè)計(jì)出的動態(tài)規(guī)劃算法的性能也迥然不同。改進(jìn)狀態(tài)表示可以減少狀態(tài)總數(shù)，進(jìn)而降低算法的時(shí)間復(fù)雜度。在降低算法的時(shí)間復(fù)雜度的同時(shí)，也降低了算法的空間復(fù)雜 7度。因此，減少狀態(tài)總數(shù)在動態(tài)規(guī)劃的優(yōu)化中占有重要的地位。 2、選擇適當(dāng)?shù)囊?guī)劃方向： 動態(tài)規(guī)劃方法的實(shí)現(xiàn)中，規(guī)劃方向的選擇主要有

32、兩種：順推和逆推。在有些情況下，選取不同的規(guī)劃方向，程序的時(shí)間效率也有所不同。一般地，若初始狀態(tài)確定，目標(biāo)狀態(tài)不確定，則應(yīng)考慮采用順推，反之，若目標(biāo)狀態(tài)確定，而初始狀態(tài)不確定，就應(yīng)該考慮采用逆推。那么，若是初始狀態(tài)和目標(biāo)狀態(tài)都已確定，一般情況下順推和逆推都可以選用，但是，能否考慮選用雙向規(guī)劃呢？雙向搜索的方法已為大家所熟知，它的主要思想是：在狀態(tài)空間十分龐大，而初始狀態(tài)和目標(biāo)狀態(tài)又都已確定的情況下，由于擴(kuò)展的狀態(tài)量是指數(shù)級增長的，于是為了減少狀態(tài)的規(guī)模，分別從初始狀態(tài)和目標(biāo)狀態(tài)兩個(gè)方向進(jìn)行擴(kuò)展，并在兩者的交匯處得到問題的解。上述優(yōu)化思想能否也應(yīng)用到動態(tài)規(guī)劃之中呢？來看下面這個(gè)例子。例二、 Di

33、vide (Merc2000) 問題描述有價(jià)值分別為1.6的大理石各a1.6塊，現(xiàn)要將它們分成兩部分，使得兩部分價(jià)值和相等，問是否可以實(shí)現(xiàn)。其中大理石的總數(shù)不超過20000。(英文試題詳見附件) 算法分析令S=(i*ai)，若S為奇數(shù)，則不可能實(shí)現(xiàn)，否則令Mid=S/2，則問題轉(zhuǎn)化為能否從給定的大理石中選取部分大理石，使其價(jià)值和為Mid。這實(shí)際上是母函數(shù)問題，用動態(tài)規(guī)劃求解也是等價(jià)的。 mi, j，0i6，0jMid，表示能否從價(jià)值為1.i的大理石中選出部分大理石，使其價(jià)值和為j，若能，則用true表示，否則用false表示。則狀態(tài)轉(zhuǎn)移方程為： mi, j=mi, j OR mi-1,j-i*

34、k (0kai)規(guī)劃的邊界條件為：mi,0=true； 0i6若mi, Mid=true，0i6，則可以實(shí)現(xiàn)題目要求，否則不可能實(shí)現(xiàn)。我們來分析上述算法的時(shí)間性能，上述算法中每個(gè)狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)為ai，每次狀態(tài)轉(zhuǎn)移的時(shí)間為O(1)，而狀態(tài)總數(shù)是所有值為true的狀態(tài)的總數(shù)，實(shí)際上就是母函數(shù)中項(xiàng)的數(shù)目。算法優(yōu)化實(shí)踐發(fā)現(xiàn)：本題在i較小時(shí)，由于可選取的大理石的價(jià)值品種單一，數(shù)量也較少，因此值為true的狀態(tài)也較少，但隨著i的增大，大理石價(jià)值品種和數(shù)量的增多，值為true的狀態(tài)也急劇增多，使得規(guī)劃過程的速度減慢，影響了算法的時(shí)間效率。另一方面，我們注意到我們關(guān)心的僅是能否得到價(jià)值和為Mid的值為t

35、rue的狀態(tài)，那么，我們能否從兩個(gè)方向分別進(jìn)行規(guī)劃，分別求出從價(jià)值為1.3的大理石中選出部分大理石所能獲得的所有價(jià)值和，和從價(jià)值為4.6的大理石中選出部分大理石所能獲得的所有價(jià)值和。最后通過判斷兩者中是否存在和為Mid的價(jià)值和，由此，可以得出問題的解。狀態(tài)轉(zhuǎn)移方程改進(jìn)為：當(dāng)i3時(shí)： mi, j=mi, j OR mi-1,j-i*k (1kai)當(dāng)i>3時(shí)：mi, j=mi, j OR mi+1,j-i*k (1kai)規(guī)劃的邊界條件為：mi,0=true； 0i7這樣，若存在k，使得m3,k=true, m4,Mid-k=true，則可以實(shí)現(xiàn)題目要求，否則無法實(shí)現(xiàn)。（程序及優(yōu)化前后的運(yùn)

36、行結(jié)果比較見附件）從上圖可以看出雙向動態(tài)規(guī)劃與單向動態(tài)規(guī)劃在計(jì)算的狀態(tài)總數(shù)上的差異?；仡櫛绢}的優(yōu)化過程可以發(fā)現(xiàn)：本題的實(shí)際背景與雙向搜索的背景十分相似，同樣有龐大的狀態(tài)空間，有確定的初始狀態(tài)和目標(biāo)狀態(tài)，狀態(tài)量都迅速增長，而且可以實(shí)現(xiàn)交匯的判斷。因此，由本題的優(yōu)化過程，我們認(rèn)識到，雙向擴(kuò)展以減少狀態(tài)量的方法不僅適用于搜索，同樣適用于動態(tài)規(guī)劃。這種在不同解題方法中，尋找共通的屬性，從而借用相同的優(yōu)化思想，可以使我們不斷創(chuàng)造出新的方法。3.2 減少每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)：在使用動態(tài)規(guī)劃方法解題時(shí)，對當(dāng)前狀態(tài)的計(jì)算都是進(jìn)行一些決策并引用相應(yīng)的已經(jīng)計(jì)算過的狀態(tài)，這個(gè)過程稱為“狀態(tài)轉(zhuǎn)移”。因此，每個(gè)狀態(tài)可能

37、做出的決策數(shù)，也就是每個(gè)狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)是決定動態(tài)規(guī)劃算法時(shí)間復(fù)雜度的一個(gè)重要因素。本節(jié)將討論減少每個(gè)狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)的一些方法。1、四邊形不等式和決策的單調(diào)性例三、石子合并問題(NOI95)問題描述在一個(gè)操場上擺放著一排n（n20）堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應(yīng)的合并方案。算法分析這道題是動態(tài)規(guī)劃的經(jīng)典應(yīng)用。由于最大得分和最小得分是類似的，所以這里僅對最小得分進(jìn)行討論。設(shè)n堆石子依次編號為1，2，.，n。各堆石子數(shù)為d1.n，則動態(tài)規(guī)劃的

38、狀態(tài)表示為： mi,j，1ijn，表示合并di.j所得到的最小得分，則狀態(tài)轉(zhuǎn)移方程和邊界條件為： mi,j=0 i=jjmi,j=minmi,k-1+mk,j+i<kjdll=iij同時(shí)令si,j=k，表示合并的斷開位置，便于在計(jì)算出最優(yōu)值后構(gòu)造出最優(yōu)解。ji上式中dl的計(jì)算，可在預(yù)處理時(shí)計(jì)算ti=l=ijdj，i=1.n；t0=0, 則： j=1dl=tj-ti-1l=i上述算法的狀態(tài)總數(shù)為O(n2)，每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(n)，每次狀態(tài)轉(zhuǎn)移的時(shí)間為O(1)，所以總的時(shí)間復(fù)雜度為O(n3)。算法優(yōu)化當(dāng)函數(shù)wi,j滿足wi,j+wi',j'wi',j+wi,j

39、',ii'jj'時(shí)，稱w滿足四邊形不等式。當(dāng)函數(shù)wi,j滿足wi,jwi,j ,ii'jj'時(shí)稱w關(guān)于區(qū)間包含關(guān)系單調(diào)。j2在石子歸并問題中，令wi,j=可知wi,j滿足單調(diào)性。 dl，則wi,j滿足四邊形不等式，同時(shí)由di0,ti0l=imi,j=0 i=jmi,j=minmi,k-1+mk,j+wi,j i<j i<kj對于滿足四邊形不等式的單調(diào)函數(shù)w，可推知由遞推式定義的函數(shù)mi,j也滿足四邊形不等式，即mi,j+mi',j'mi',j+mi,j',ii'jj'。這一性質(zhì)可用數(shù)學(xué)歸納法證明

40、如下：我們對四邊形不等式中“長度”l=j-i進(jìn)行歸納：當(dāng)i=i或j=j時(shí)，不等式顯然成立。由此可知，當(dāng)l1時(shí)，函數(shù)m滿足四邊形不等式。下面分兩種情形進(jìn)行歸納證明：情形1：i<i=j<j在這種情形下，四邊形不等式簡化為如下的反三角不等式：mi,j+mj,j mi,j，設(shè)k=maxp | mi,j=mi,p-1+mp,j+wi,j ，再分兩種情形kj或k>j。下面只討論kj，k>j的情況是類似的。情形1.1：kj，此時(shí)：mi,j+mj,j'wi,j+mi,k-1+mk,j+mj,j'wi,j'+mi,k-1+mk,j+mj,j'wi,j

41、9;+mi,k-1+mk,j'=mi,j'情形2：i<i<j<j設(shè) y=maxp | mi,j=mi,p-1+mp,j+wi,j z=maxp | mi,j=mi,p-1+mp,j+wi,j 仍需再分兩種情形討論，即zy或z>y。下面只討論zy，z>y的情況是類似的。由i<zyj有：mi,j+mi',j'wi,j+mi,z-1+mz,j+wi',j'+mi',y-1+my,j'wi,j'+wi',j+mi',y-1+mi,z-1+mz,j+my,j'wi,j

42、9;+wi',j+mi',y-1+mi,z-1+my,j+mz,j'=mi,j'+mi',j綜上所述，mi,j滿足四邊形不等式。令si,j=maxk | mi,j=mi,k-1+mk,j+wi,j 由函數(shù)mi,j滿足四邊形不等式可以推出函數(shù)si,j的單調(diào)性，即si,jsi,j+1si+1,j+1, ij當(dāng)i=j時(shí)，單調(diào)性顯然成立。因此下面只討論i<j的情形。由于對稱性，只要證明si,jsi,j+1。 令mki,j=mi,k-1+mk,j+wi,j。要證明si,jsi,j+1，只要證明對于所有i<kkj且mki,jmki,j，有：mki,j+1

43、mki,j+1。事實(shí)上，我們可以證明一個(gè)更強(qiáng)的不等式mki,j-mki,jmki,j+1-mki,j+1也就是： mki,j+mki,j+1mki,j+1+mki,j利用遞推定義式將其展開整理可得：mk,j+mk,j+1mk,j+mk,j+1，這正是kkj<j+1時(shí)的四邊形不等式。綜上所述，當(dāng)w滿足四邊形不等式時(shí)，函數(shù)si,j具有單調(diào)性。于是，我們利用si,j的單調(diào)性，得到優(yōu)化的狀態(tài)轉(zhuǎn)移方程為：mi,j=0 i=jmi,j=si,j-1ksi+1,jminmi,k-1+mk,j+wi,j i<j用類似的方法可以證明，對于最大得分問題，也可采用同樣的優(yōu)化方法。改進(jìn)后的狀態(tài)轉(zhuǎn)移方程所需

44、的計(jì)算時(shí)間為n-1O i=1n-12(1+si+1,j-si,j-1)=O(n-i+si+1,n-s1,n-i) =On j=i+1i=1n()（程序及優(yōu)化前后的運(yùn)行結(jié)果比較見附件）上述方法利用四邊形不等式推出最優(yōu)決策的單調(diào)性，從而減少每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)，降低算法的時(shí)間復(fù)雜度。 上述方法是具有普遍性的。對于狀態(tài)轉(zhuǎn)移方程與式類似，且wi,j滿足四邊形不等式的動態(tài)規(guī)劃問題，都可以采用相同的優(yōu)化方法，如最優(yōu)二叉排序樹（NOI96）等。下面再舉一例。例四、郵局(IOI2000) 問題描述按照遞增順序給出一條直線上坐標(biāo)互不相同的n個(gè)村莊，要求從中選擇p個(gè)村莊建立郵局，每個(gè)村莊使用離它最近的那個(gè)郵局，使

45、得所有村莊到各自所使用的郵局的距離總和最小。試編程計(jì)算最小距離和，以及郵局建立方案。算法分析本題也是一道動態(tài)規(guī)劃問題，詳細(xì)分析請看文本附件（郵局解題報(bào)告）。將n個(gè)村莊按坐標(biāo)遞增依次編號為1，2，n，各個(gè)郵局的坐標(biāo)為d1.n，狀態(tài)表示描述為：mi,j表示在前j個(gè)村莊建立i個(gè)郵局的最小距離和。所以，mp,n即為問題的解，且狀態(tài)轉(zhuǎn)移方程和邊界條件為：m1,j=w1,jmi,j=i-1kj-1minmi-1,k+wk+1,j ij其中wi,j表示在di.j之間建立一個(gè)郵局的最小距離和，可以證明，當(dāng)僅建立一個(gè)郵局時(shí)，最優(yōu)解出現(xiàn)在中位數(shù)，即設(shè)建立郵局的村莊為k，則k=(i+j)/2或k=(i+j)/2，于

46、是，我們有：jwi,j=|dl-dk| ， kl=i=(i+j)/2或k=(i+j)/2 10同時(shí)，令si,j=k，記錄使用前i-1個(gè)郵局的村莊數(shù)，便于在算出最小距離和之后構(gòu)造最優(yōu)建立方案。上述算法中wi,j可通過O(n)時(shí)間的預(yù)處理，在O(1)的時(shí)間內(nèi)算出，所以，該算法的狀態(tài)總數(shù)為O(n*p)，每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(n)，每次狀態(tài)轉(zhuǎn)移的時(shí)間為O(1)，該算法總的時(shí)間復(fù)雜度為O(p*n)。算法優(yōu)化本題的狀態(tài)轉(zhuǎn)移方程與式十分相似，因此我們猜想其決策是否也滿足單調(diào)性，即si-1,jsi,jsi,j+1首先，我們來證明函數(shù)w滿足四邊形不等式，即：wi,j+wi',j'wi'

47、;,j+wi,j' ,ii'jj' 2設(shè)y=(i'+j)/2，z=(i+j')/2，下面分為兩種情形，zy或z>y，下面僅討論zy，z>y的情況是類似的。由izyj有：jj'wi,j+wi',j'j|dl-dz|+|dl-dy|l=ij'l=i'j'j'|dl-dz|+|dl-dy|+l=ij'l=i'jl=j+1|dl-dz|-l=j+1|dl-dy|=|dl-dz|+|dl-dy|l=il=i'=wi',j+wi,j'接著，我們用數(shù)學(xué)歸納法證明

48、函數(shù)m也滿足四邊形不等式。對四邊形不等式中“長度”l=j-i進(jìn)行歸納：當(dāng)i=i或j=j時(shí)，不等式顯然成立。由此可知，當(dāng)l1時(shí)，函數(shù)m滿足四邊形不等式。 下面分兩種情形進(jìn)行歸納證明：情形1：i<i=j<j，即mi,j+mj,j mi,j，設(shè)k=maxp | mi,j=mi,p-1+mp,j+wi,j ，再分兩種情形kj或k>j。下面只討論kj，k>j的情況是類似的。mi,j+mj,j'mi-1,k+wk+1,j+mj-1,j-1+wj,j'mi-1,k+wk+1,j'=mi,j'情形2：i<i<j<j設(shè) y=maxp |

49、mi,j=mi-1,p+wp+1,j z=maxp | mi,j=mi-1,p+wp+1,j 仍需再分兩種情形討論，即zy或z>y。情形2.1，當(dāng)zy<j<j時(shí)：mi,j+mi',j'mi'-1,y+wy+1,j'+mi-1,z+wz+1,jmi'-1,y+mi-1,z+wy+1,j+wz+1,j'=mi',j+mi,j'情形2.2，當(dāng)i-1<i-1y<z<j時(shí)：mi,j+mi',j'mi-1,y+wy+1,j+mi'-1,z+wz+1,j'mi-1,z+mi&#

50、39;-1,y+wy+1,j+wz+1,j'=mi,j'+mi',j最后，我們證明決策si,j滿足單調(diào)性。為討論方便，令mki,j=mi-1,k+wk+1,j；我們先來證明si-1,jsi,j，只要證明對于所有ik<k<j且mki-1,jmki-1,j，有：mki,jmki,j。類似地，我們可以證明一個(gè)更強(qiáng)的不等式 mki-1,j-mki-1,jmki,j-mki,j也就是： mki-1,j+mki,jmki,j+mki-1,j利用遞推定義式展開整理的：mi-2,k+mi-1,kmi-1,k+mi-2,k，這就是i-2<i-1<k<k時(shí)m的

51、四邊形不等式。我們再來證明si,jsi,j+1，與上文類似，設(shè)k<k<j，則我們只需證明一個(gè)更強(qiáng)的不等式： mki,j-mki,jmki,j+1-mki,j+1也就是： mki,j+mki,j+1mki,j+1+mki,j利用遞推定義式展開整理的：wk+1,j+wk+1,j+1wk+1,j+1+wk+1,j，這就是k+1<k+1<j<j+1時(shí)w的四邊形不等式。綜上所述，該問題的決策si,j具有單調(diào)性，于是優(yōu)化后的狀態(tài)轉(zhuǎn)移方程為： m1,j=w1,jmi,j=si-1,jksi,j+1minmi-1,k+wk+1,j ijsi,j=k同上文所述，優(yōu)化后的算法時(shí)間復(fù)雜

52、度為O(n*p)。（程序及優(yōu)化前后的運(yùn)行結(jié)果比較見附件） 四邊形不等式優(yōu)化的實(shí)質(zhì)是對結(jié)果的充分利用。它通過分析狀態(tài)值之間的特殊關(guān)系，推出了最優(yōu)決策的單調(diào)性，從而在計(jì)算當(dāng)前狀態(tài)時(shí)，利用已經(jīng)計(jì)算過的狀態(tài)所做出的最優(yōu)決策，減少了當(dāng)前的決策量。這就啟發(fā)我們，在應(yīng)用動態(tài)規(guī)劃解題時(shí)，不僅可以實(shí)現(xiàn)狀態(tài)值的充分利用，也可以實(shí)現(xiàn)最優(yōu)決策的充分利用。這實(shí)際上是從另一個(gè)角度實(shí)現(xiàn)了“減少冗余”。 2、決策量的優(yōu)化：通過分析問題最優(yōu)解所具備的性質(zhì)，從而縮小有可能產(chǎn)生最優(yōu)解的決策集合，也是減少每個(gè)狀態(tài)可能轉(zhuǎn)移的狀態(tài)數(shù)的一種方法。大家所熟悉的NOI96中的添加號問題，正是從“所得的和最小”這一原則出發(fā)，僅在等分點(diǎn)的附近添加

53、號，從而大大減少了每個(gè)狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)，降低了算法的時(shí)間復(fù)雜度。讓我們在再來看一例。例五、石子歸并的最大得分問題 問題描述見例三，本例只考慮最大得分問題。算法分析設(shè)n堆石子依次編號為1，2，.，n。各堆石子數(shù)為d1.n，則動態(tài)規(guī)劃的狀態(tài)表示為： mi,j，1ijn，表示合并di.j所得到的最大得分，則狀態(tài)轉(zhuǎn)移方程和邊界條件為： mi,j=0 i=jjmi,j=maxmi,k-1+mk,j+i<kjdl ij l=i同時(shí)令si,j=k，表示合并的斷開位置，便于在計(jì)算出最優(yōu)值后構(gòu)造出最優(yōu)解。該算法的時(shí)間復(fù)雜度為O(n3)。算法優(yōu)化仔細(xì)分析問題，可以發(fā)現(xiàn)：si,j要么等于i+1，要么等于j，即：maxmi,k-1+mk,j=maxmi,j-1,mi+1,j,i<j i<kjp-1證明可以采用反證法，設(shè)使mi,j達(dá)到最大值的斷開位置為p，且i+1<p<j，y=jal，l=iz=al，下面分為2種情形討論。l=p情形1、yz由p<j，可設(shè)sp,j=k，則相應(yīng)的合并方式可以表示為：( (aiap-1) ( (a