深度優(yōu)先搜索優(yōu)化——向期中

1、深度優(yōu)先搜索的優(yōu)化長(zhǎng)郡中學(xué) 向期中深度優(yōu)先搜索在解決問(wèn)題的時(shí)候，通過(guò)一定的順序，依次枚舉出問(wèn)題可能存在的方案，并得出其中最優(yōu)的方案的方法，被我們稱(chēng)之為搜索。在由已有的狀態(tài)拓展出新的狀態(tài)時(shí)，后拓展出的節(jié)點(diǎn)優(yōu)先拓展的搜索順序，被稱(chēng)為深度優(yōu)先搜索。相必各位對(duì)深度優(yōu)先搜索都并不陌生，所以我們今天討論的重點(diǎn)在于對(duì)深度優(yōu)先搜索的優(yōu)化。優(yōu)化的方向搜索問(wèn)題一般求的是所有可行方案中最優(yōu)的一種方案，所以我們有兩個(gè)下手方向：1）可行：有很多方案到最后我們才發(fā)現(xiàn)是不行的，但是這些方案在一開(kāi)始就已經(jīng)決定的是不行的，所以盡早的判斷出一個(gè)方案是否可行，對(duì)于問(wèn)題的優(yōu)化是很明顯的。2）最優(yōu)：在一些情況下，無(wú)論之后如何決策，得出

2、的方案都一定不比當(dāng)前所得到的最優(yōu)方案要優(yōu)，那么這些方案都沒(méi)有了訪(fǎng)問(wèn)的必要，可以進(jìn)行剪枝。而在大多數(shù)情況下，這兩種剪枝，都是同時(shí)進(jìn)行的。 小Z的生日就要到了，他的朋友小A想要幫他制作一個(gè)生日蛋糕，根據(jù)小Z的喜好，小A對(duì)蛋糕制作師提出了如下要求： 蛋糕由m個(gè)圓柱形組成，設(shè)從下往上數(shù)第i(1=i=m)層蛋糕是半徑為Ri, 高度為Hi的圓柱。 要求當(dāng)iRi+1且HiHi+1。 找出蛋糕的制作方案（適當(dāng)?shù)腞i和Hi的值），使S最小。 (除Q外，以上所有數(shù)據(jù)皆為正整數(shù))圓柱公式 V=R2H S側(cè)=2RH S底=R2生日蛋糕 321*2*min)*2*(1312)*(1111min1111，滿(mǎn)足其中，mii

3、imiiijijimiiiiHRRRQHRRRSmjiandHHmjiandRRHRRV解析法？ 轉(zhuǎn)變思路，搜索？數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)用( i , Ri , Hi , Vi , Si )表示第i層蛋糕的一個(gè)狀態(tài)。其中Ri ,Hi分別為第i層蛋糕的半徑和高，Vi , Si分別表示做完第i層蛋糕后剩下的蛋糕體積和當(dāng)前蛋糕的表面積?？梢?jiàn)， 初始狀態(tài)：(1,R1,H1,n-R1*R1*H1,R1*R1+2*R1*H1) 目標(biāo)狀態(tài)：(m,Rm,Hm,0,Sm)于是，我們的目標(biāo)是找到一條從初始狀態(tài)到任意目標(biāo)狀態(tài)的路徑，并且Sm最小. 擴(kuò)展的規(guī)則擴(kuò)展的規(guī)則 ( i , Ri , Hi , Vi , Si ) ( i

4、+1,Ri+1,Hi+1,Vi+1,Si+1)滿(mǎn)足: （1） Ri Ri+1 （2） Hi Hi+1 （3） Vi+1 = Vi - Ri+1* Ri+1* Hi+1 （4） Si+1 = Si + 2 * Ri+1* Hi+1確定第一層蛋糕的大小根據(jù)上一層蛋糕的大小確定下一層蛋糕該怎么做看是否符合條件 1）是否做到了m層 2）是否最終體積為0 3）是否當(dāng)前面積最小若上述條件成立，則保留當(dāng)前最優(yōu)值，否則繼續(xù)做下一層蛋糕，若重做蛋糕基本算法Search (i, Ri , Hi , Si , Vi) 對(duì)每層蛋糕進(jìn)行搜索if (i=m) and (Vi =0) then 更新最優(yōu)值else for

5、Ri + 1Ri -1 downto i for Hi + 1Hi -1 downto i Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - Ri + 1* Ri + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) Problem-Cake枚舉所有的初始狀態(tài) - 第一層蛋糕的大小 for R1m to sqrt ( n ) do /*假設(shè) H1=1，只做一層蛋糕 */ for H1n div (R1*R1) downto m do S1=2 * R1* H1+ R1* R1 V1=n - R1* R1

6、 * H1 Search (1, R1, H1, S1, V1) 優(yōu)化？（1 1）因?yàn)橹烙嘞碌牡案怏w積）因?yàn)橹烙嘞碌牡案怏w積, ,因此可以估算一下余下側(cè)面積因此可以估算一下余下側(cè)面積, , 這樣我們可以就加入如下剪枝條件這樣我們可以就加入如下剪枝條件: : if if 當(dāng)前的表面積當(dāng)前的表面積 + + 余下的側(cè)面積余下的側(cè)面積 當(dāng)前最優(yōu)值當(dāng)前最優(yōu)值 then exitthen exit 設(shè)已經(jīng)做了設(shè)已經(jīng)做了i i層蛋糕層蛋糕, ,則還需做則還需做m-im-i層層, , S Si i：為第：為第i i層蛋糕的側(cè)面積層蛋糕的側(cè)面積, , FSFSi i：余下的側(cè)面積：余下的側(cè)面積, ,怎么求怎

7、么求FSFSi i ? ? 因?yàn)橐驗(yàn)? : 2Vi= 2Ri+1 * Ri+1 * Hi+1 + .+ 2Rm * Rm * Hm = Ri+1 * Si+! + .+ Rm * Sm Ri+1 * (Si+1+ .+ Sm) = Ri+1 * FSi 所以所以: : FSi 2Vi / Ri+1 因此剪枝條件為：因此剪枝條件為： if Si-1 + 2 * Vi-1 / Ri 當(dāng)前最優(yōu)值當(dāng)前最優(yōu)值 then exit優(yōu)化？(2)如果剩下的蛋糕材料太少，不能保證做到m層,那么沒(méi)有必要繼續(xù)往下做了，設(shè)，最m層半徑和高都為1，Rm=Hm=1第m-1層半徑和高都為2，Rm-1=Hm-1=2 第 i

8、+1層半徑和高都為i, Ri = Hi = m i 這樣， 余下的m-i層的最小體積為imkikMIN13因此,剪枝條件為, if Vi當(dāng)前最優(yōu)值當(dāng)前最優(yōu)值 then exit; 剪枝剪枝1 if Vi MINi then exit; 剪枝剪枝2 if Vi MAXi then exit; 剪枝剪枝3 if im then for Ri + 1 Ri downto ifor Hi + 1min(Vi div (Ri + 1*Ri + 1), Hi) downto i Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - Ri + 1* Ri + 1* Hi + 1

9、Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) Else if Vi =0 then 更新最優(yōu)值更新最優(yōu)值Problem-Cake 1. 計(jì)算計(jì)算MINi和和MAXi R,H ; 2. for R1m to sqrt ( n ) do /*假設(shè)假設(shè) H1=1，只做一層蛋糕，只做一層蛋糕 */ 3. for H1n div (R1*R1) downto m do 4. S1=2 * R1* H1+ R1* R1 5. V1=n - R1* R1 * H1 6. Search (1, R1, H1, S1, V1) 7. 小節(jié)可行性剪枝 剪枝2：if Vi

10、當(dāng)前最優(yōu)值 then exit 剪枝原則 正確、高效深度搜索消耗時(shí)間深度搜索消耗時(shí)間 每個(gè)節(jié)點(diǎn)操作系數(shù)每個(gè)節(jié)點(diǎn)操作系數(shù) 節(jié)點(diǎn)個(gè)數(shù)節(jié)點(diǎn)個(gè)數(shù) 優(yōu)化 1）減少節(jié)點(diǎn)個(gè)數(shù)這就是剪枝優(yōu)化剪枝優(yōu)化； 2）減少每個(gè)節(jié)點(diǎn)的操作系數(shù)即程序操作量程序操作量。15數(shù)碼問(wèn)題在44的棋盤(pán)上，擺有15個(gè)棋子，每個(gè)棋子上標(biāo)有1至15的某一數(shù)字。棋盤(pán)中留有一個(gè)空格(空格用0表示)。空格周?chē)钠遄涌梢砸频娇崭裰?。要求解的?wèn)題是：給出一種初始布局（初始狀態(tài)）和目標(biāo)面局（目標(biāo)狀態(tài)），找到一種最少步驟的移動(dòng)方法，實(shí)現(xiàn)從初始布局到目標(biāo)布局的轉(zhuǎn)變。12345678910111213141500123456789101112131415引入

11、迭代加深算法：從小到大枚舉ans，用深搜判斷ans是否可行。因?yàn)閍ns越小越容易進(jìn)行可行性剪枝。因?yàn)閍ns枚舉出來(lái)了，所以不存在最優(yōu)性剪枝。其實(shí)也可以理解成枚舉ans，更好地進(jìn)行最優(yōu)性剪枝。搜索順序的優(yōu)化就要根據(jù)題目討論了。估價(jià)函數(shù)s問(wèn)題的某種狀態(tài)。h*(s)s到目標(biāo)的實(shí)際最短距離。h(s)s的估價(jià)函數(shù)，表示s到目標(biāo)距離的下界，h(s)=h*(s)，若h函數(shù)是相容的，則還需要滿(mǎn)足h(s1)=ans，則當(dāng)前狀態(tài)舍去，進(jìn)行最優(yōu)性剪枝。本題的估價(jià)函數(shù)考慮到每次移動(dòng)時(shí)除0以外的其他數(shù)最多有一個(gè)向目標(biāo)位置靠近一格。所以h(s)=d(k,k) 1=k=15h(s)滿(mǎn)足兩個(gè)條件h(s)=h*(s)h(s1)

12、=h(s2)+c(s1,s2)A*算法與IDA*算法將估價(jià)函數(shù)運(yùn)用到廣搜的算法稱(chēng)為A*算法，需用堆來(lái)實(shí)現(xiàn)。A*算法是理論上時(shí)間最優(yōu)的算法，但所需空間太大。為了解決A*算法的空間問(wèn)題，IDA*算法被提出，它是將估價(jià)函數(shù)與迭代加深算法結(jié)合起來(lái)的算法。所以此題用深搜，通過(guò)IDA*算法進(jìn)行優(yōu)化即可。IDA*算法練習(xí)題給你一個(gè)1n的任意排列，你需要進(jìn)行最少的操作將它變成從小到大的排列。一次操作是指將排列中的任一段剪貼出來(lái)并粘貼到任意位置。如123764598，將其中的45取出來(lái)，放到3的后面，則變?yōu)?23457698分析這是一道IDA*的練習(xí)題，我們直接分析估計(jì)函數(shù)，搜索部分因?yàn)楸容^基礎(chǔ)，這里略過(guò)。首先

13、很容易想到h(s)=后繼正確的個(gè)數(shù)。但這樣h(s)并不滿(mǎn)足相容性，考慮到我們一次操作會(huì)改變3個(gè)數(shù)的后繼，所以將h(s)/3即可。軟件安裝（NOI98）軟件安裝通常是一件令人頭疼的事。軟件一般都包括若干個(gè)相對(duì)獨(dú)立的部分（稱(chēng)為“組件”），在安裝的時(shí)候由用戶(hù)決定安裝哪些部分。并且，這些相對(duì)獨(dú)立的組件之間在安裝時(shí)有一定的先后順序要求。 由于當(dāng)代的個(gè)人計(jì)算普遍安裝了軟盤(pán)驅(qū)動(dòng)器，所以軟件的最流行的載體形式是軟盤(pán)。然而，由于軟盤(pán)的容量有限，稍大一些的軟件就無(wú)法用一張軟盤(pán)裝下。這時(shí)，這些軟件往往要用很多張軟盤(pán)來(lái)存儲(chǔ)。每張軟盤(pán)上存儲(chǔ)了軟件的一個(gè)或多個(gè)組件。這些軟盤(pán)成為軟件的安裝盤(pán)。軟件安裝（NOI98）由于軟件

14、的各個(gè)組件分散在不同的軟盤(pán)上，而在安裝時(shí)又有一定的先后順序要求，所以很容易發(fā)生要求用戶(hù)反復(fù)換盤(pán)的情況。而計(jì)算機(jī)用戶(hù)在安裝軟件的時(shí)候，最反感的就是反復(fù)在軟盤(pán)之間切換：找盤(pán)，插盤(pán)，取盤(pán)，找盤(pán)，插盤(pán)，取盤(pán) 一切都顯得那么瑣碎和無(wú)序，因此，有必要對(duì)軟件安裝盤(pán)的制作提出下述要求： 永遠(yuǎn)不要讓用戶(hù)將一張軟盤(pán)插入兩次。更精確的，要求對(duì)安裝盤(pán)從1開(kāi)始順序編號(hào)，使得安裝的時(shí)候，用戶(hù)只要按順序插入磁盤(pán)即可。出于經(jīng)濟(jì)的考慮，通常要求安裝盤(pán)的總數(shù)最少。寫(xiě)一個(gè)程序，對(duì)于給定的軟件，制定最優(yōu)的安裝盤(pán)方案。分析基本概念：（1）組件的前趨：一個(gè)組件安裝前應(yīng)預(yù)先安裝的組件集合稱(chēng)為該組件的前趨，而這個(gè)組件前趨的前趨不算這個(gè)組件的

15、前趨。例如：1是2的前趨，2是3的前趨，但1不是3的前趨。（2）影響制約：I對(duì)J有影響制約是指I是J的前趨。（3）組件的后繼：一個(gè)組件可以直接影響制約的組件集合稱(chēng)為該組件的后繼。分析此題初看好像可以用動(dòng)態(tài)規(guī)劃，但分析一下即知，它顯然不符合動(dòng)態(tài)規(guī)劃的特征：無(wú)后效性。因?yàn)槊繌埍P(pán)不一定放滿(mǎn)，且組件于組件之間有制約關(guān)系，所以一個(gè)組件的選擇將影響以后的組件，有明顯的后效性；由于是求最優(yōu)解，且要輸出存放情況，數(shù)學(xué)方法就不用考慮了。它的建模不符合任何圖論模型。左思右想，是最優(yōu)化的序列問(wèn)題，且數(shù)據(jù)范圍不算太大，最后只有用搜索了。我們定義如下變量MaxCap：Longint 每張軟盤(pán)的最大容量；N：Intege

16、r 組件數(shù)；MinDisk: array0.MaxN of Integer； 最少的軟盤(pán)數(shù)；Father： array0.MaxN of Integer； FatherI指組件I的所有前趨；Module： array0.MaxN of Integer； ModuleI指第I次選擇的軟件；ParModule: array0.MaxN of Integer； 存儲(chǔ)Module的最優(yōu)值；ModCap: array0.MaxN of Integer； ModCapI指組件I的字節(jié)數(shù)；Choose: array0.MaxN of Boolean； ChooseI為true表示組件I未選過(guò)，false反之

17、；Top: array0.MaxN, 0.MaxN of 0.1； TopI，J是指J對(duì)I有影響制約；Next： array0.MaxN, 0.MaxN of Integer； NextI是指I的所有后繼。搜索方式由于組件有前后制約關(guān)系，且軟盤(pán)數(shù)一定小于等于組件數(shù)，所以搜索應(yīng)模擬將組件依次放入軟盤(pán)中的過(guò)程，即當(dāng)前應(yīng)選擇那個(gè)組件，選定后再看它是否能放入當(dāng)前軟盤(pán)，不行則加一張軟盤(pán)，繼續(xù)放 再?gòu)闹姓页鲇密洷P(pán)最少的序列。這樣就很容易用深度優(yōu)先搜索，只需傳幾個(gè)變量：Order：Integer 搜索的層數(shù)，即當(dāng)前選第Order張軟盤(pán)；Num：Integer 當(dāng)前所用的軟盤(pán)數(shù)；Free：Longint 當(dāng)前

18、這張軟盤(pán)的剩余空間；LeftModCap：Extended 剩余軟盤(pán)的總字節(jié)；procedure SENSOR(Order, Num: Integer；Free: Longint； LeftModCap：Extended)； var I, J: Integer；begin if 所有組件搜完then begin if MinDisk Free then SENSOR(Order + 1,Num + 1,MaxCap - ModCapI,LeftModCap - ModCapI)增加一張軟盤(pán)，繼續(xù)搜索 else SENSOR(Order + 1,Num,Free - ModCapI,LeftMo

19、dCap - ModCapI)；繼續(xù)搜索這張盤(pán) ChooseI := true； ModuleOrder := 0； for J := 1 to NextI,0 do Inc(FatherNextI,J)；還原Choose，Module，F(xiàn)ather數(shù)組： end；end；復(fù)雜度估計(jì)編程復(fù)雜度：為一般搜索，較簡(jiǎn)單?？臻g復(fù)雜度：此題的范圍較小，數(shù)組，鄰接表，稀疏矩陣 不必對(duì)其做特殊優(yōu)化。時(shí)間復(fù)雜度：此題用搜索，層數(shù)為MaxN層，每層的時(shí)間復(fù)雜度為MaxN，所以程序時(shí)間復(fù)雜度為MaxN！，即100！。這樣的復(fù)雜度無(wú)論如何是承受不了的。因此，剪枝優(yōu)化就必不可少了。分支定界描述：當(dāng)你搜索到任意解之后，

20、如果不能很好的利用這一結(jié)果就太浪費(fèi)了。應(yīng)當(dāng)如何運(yùn)用呢？如果以后的搜索中，當(dāng)前序列如何繼續(xù)都不可能搜出比當(dāng)前已經(jīng)搜到的最優(yōu)解更好的解（稱(chēng)為劣序）就不必繼續(xù)了。但如何判斷是否為為劣序呢？實(shí)現(xiàn)：如果已搜到第Order個(gè)，沒(méi)有選的組件的總和為L(zhǎng)eftModCap，當(dāng)前軟盤(pán)的剩余容量為Free，那么總軟件數(shù)不可能比P少（P:=LeftModCap div MaxCap；if LeftModCap mod MaxCap Free then P := P + 1）。這樣可以免去一些劣序，節(jié)省很多時(shí)間。分支定界證明：設(shè)所有組件的字節(jié)總和為M，所有軟盤(pán)的剩余空間總和為Waste（軟盤(pán)的剩余空間：軟盤(pán)沒(méi)有裝組件的

21、空間）。軟盤(pán)數(shù)（MWaste）divMaxCap，M與MaxCap是一定的，所以剩余空間最小，軟盤(pán)數(shù)也最少。假設(shè)剩余的軟盤(pán)沒(méi)有制約關(guān)系，且剩余組件可以一個(gè)挨一個(gè)的放入（在中間不會(huì)出現(xiàn)剩余空間，最后可以出現(xiàn)剩余空間），組件所需的軟盤(pán)一定最少。如果這種理想最少的軟盤(pán)數(shù)已用的軟盤(pán)數(shù)還比已搜索到的軟盤(pán)最優(yōu)解還多或等于，就沒(méi)必要繼續(xù)了，因?yàn)椴豢赡艹霈F(xiàn)比這種情況跟優(yōu)的情況了。劣者靠后描述：劣者靠后，顧名思義就是性質(zhì)不佳的組件靠后放。當(dāng)如何定義性質(zhì)不佳呢？又如何保證不丟失最優(yōu)解呢？實(shí)現(xiàn)：如果當(dāng)前組件放在當(dāng)前軟盤(pán)中之后，此張軟盤(pán)再也不能放其他組件，且這組件無(wú)后繼，而這個(gè)組件又不是可以放在當(dāng)前軟件中的最大的組件

22、，那么它是就劣者，就不應(yīng)該在當(dāng)前放入這張軟盤(pán)。劣者靠后證明：可以用假設(shè)法證明；假設(shè)命題不成立：即劣者不放在此可能無(wú)法形成最優(yōu)解。設(shè)可以放在當(dāng)前軟件（設(shè)為I）中的所需空間最大的組件被編號(hào)為K。按照假設(shè)命題敘述，可能最優(yōu)解是劣者放在此，K放在以后的軟盤(pán)（設(shè)為J）中。但實(shí)際上，如果劣者放在此，K放在以后的軟盤(pán)中可以形成最優(yōu)解，那么交換二者的位置是另一種最優(yōu)解(因?yàn)镮中放劣者或K都是一個(gè)，效果一樣，而J中放劣者之后，空間更大，而且不會(huì)對(duì)其他組件產(chǎn)生影響)，所以劣者不放在此肯定可以形成最優(yōu)解。所以命題錯(cuò)誤。所以劣者必不放在此。劣者靠后其它剪枝除去可行性剪枝和最優(yōu)化剪枝之外，還有一些其他的剪枝，他們的效果

23、也都是不錯(cuò)的。接下來(lái)看一道例題。拓?fù)渑判蛎枋觯涸僖粋€(gè)軟盤(pán)中的組件，如果沒(méi)有制約關(guān)系，那么調(diào)換其順序，又將變?yōu)榱硪环N方案（此軟件有n個(gè)組件，就有N！種重復(fù)情況），而如果很多軟盤(pán)都如此，將有許多重復(fù)情況，時(shí)間復(fù)雜度將聚增。如何避免這些情況呢？實(shí)現(xiàn)：先將所有的組件按拓?fù)渑判颍ㄈ缬啥鄠€(gè)拓?fù)渑判颍我庖粋€(gè)），然后將原順序變?yōu)橥負(fù)湫蛄校ò赐負(fù)渑判蚝蟮男蛄校?，然后每張軟盤(pán)內(nèi)部組件編號(hào)（拓?fù)渑判蚝蟮木幪?hào)）的順序規(guī)定為增序，這樣即避免了重復(fù)，又不會(huì)漏解，一舉兩得。拓?fù)渑判蜃C明：假設(shè)有時(shí)必須亂序（亂序：不是增序）才可得到最優(yōu)解。因?yàn)閬y序可以得到最優(yōu)，那么將這些組件按增序也同樣可以得到最優(yōu)（因?yàn)閷㈨樞蜃優(yōu)樵鲂蚝?，?/p>

24、拓?fù)湫蛄校詢(xún)?nèi)部符合制約關(guān)系；總字節(jié)不變，仍然可以放入此軟盤(pán)；對(duì)下面幾張盤(pán)的影響制約也不變）。所以是增序也可得到最優(yōu)解。所以假設(shè)命題錯(cuò)誤。所以軟盤(pán)內(nèi)的組件一定要按增序排列。（補(bǔ)充：拓?fù)湫蛄杏卸喾N，但任意一種都行，這樣應(yīng)該盡量讓后繼多的組件在前面，這樣有利于搜索，證明略）。節(jié)省空間描述：由于搜索是枚舉每一個(gè)組件，所以可能當(dāng)前軟盤(pán)下還可放入若干個(gè)組件，搜索卻選擇字節(jié)太大而無(wú)法放入這張盤(pán)的組件放入下一張盤(pán)，這張盤(pán)的空間又不會(huì)再用，所以浪費(fèi)了空間。實(shí)現(xiàn)：應(yīng)先看是否有可以放入這張軟盤(pán)的組件，沒(méi)有再枚舉放如下一張軟盤(pán)的組件，否則就不用看了。證明：假設(shè)當(dāng)前軟盤(pán)I有空間可以放J，卻要不放才能得到最有解。那么

25、將J有后面拿上來(lái)，放入I中，不會(huì)改變影響制約關(guān)系，仍然是最優(yōu)解。所以假設(shè)命題錯(cuò)誤。有空可以放一定不可空著。選用慎用1.提前貪心：貪出一個(gè)較有解，這樣有利于分支定界，也可以避免特殊數(shù)據(jù)的刁難（有時(shí)貪心的解就是最優(yōu)解）。2.隨機(jī)化：由于一般再搜索過(guò)程中，枚舉找下一個(gè)組件時(shí)，一般用循環(huán)語(yǔ)句for I := 1 to N do ，但有時(shí)數(shù)據(jù)是完全顛倒的，這樣將花去太多時(shí)間，所以可以采用隨機(jī)化，確定I是從1枚舉到N，還是從N枚舉到1，因?yàn)槭?隨機(jī)的，所以無(wú)論數(shù)據(jù)如何刁難，平均時(shí)間都差不多，不會(huì)因?yàn)閿?shù)據(jù)的選取而時(shí)間復(fù)雜度猛增。3.時(shí)間限制： 由于是搜索題，所以無(wú)論什么剪枝，都很難保證一定可以再時(shí)限內(nèi)出解，

26、且有 有些數(shù)據(jù)最優(yōu)解在時(shí)限內(nèi)已得到，只是不能確定是否為最優(yōu)，程序沒(méi)有退出，而導(dǎo)致超時(shí)。所以用時(shí)間限制可以保證不超時(shí)，但不能保證正確。源程序見(jiàn)目錄下software.pas積木搭建（IOI2000）單位立方體(unit cube)是一個(gè)111的立方體，它的所有角的x,y和z坐標(biāo)都是整數(shù)。我們稱(chēng)兩個(gè)單位立方體是連通的，當(dāng)且僅當(dāng)他們有一個(gè)公共的面；一個(gè)構(gòu)形(solid)或者是一個(gè)單位立方體，或者是由多個(gè)單位立方體組成的連通物體(如圖一所示)，它的體積就是它所含的單位立方體的個(gè)數(shù)。一塊積木(block)是一個(gè)體積不超過(guò)4的構(gòu)形。如果兩塊積木可以平移、旋轉(zhuǎn)(注意，不能成鏡像)操作變得完全一樣，我們就稱(chēng)它

27、們屬于同一類(lèi)。這樣，積木總共有12類(lèi)(如圖2所示)。圖2中積木的不同顏色僅僅是為了幫助你看清楚它的結(jié)構(gòu)，并沒(méi)有其他的含義。一個(gè)構(gòu)形可以由若干塊積木組成。如果用一些積木可以互不重疊的搭建出某個(gè)構(gòu)形，那么就稱(chēng)這些積木是這個(gè)構(gòu)形的一種分解(decomposition)。你的任務(wù)是寫(xiě)一個(gè)程序,對(duì)于給定的一組積木種類(lèi)和一個(gè)構(gòu)形S,求出境可能少的積木個(gè)數(shù),使得他們能夠搭建出構(gòu)形S。你只需給出這個(gè)最少的積木個(gè)數(shù)，以及這些積木各自所屬的種類(lèi)，而不必給出具體的搭建方案。數(shù)據(jù)結(jié)構(gòu)為描述清楚，先列出數(shù)據(jù)結(jié)構(gòu)：TPoint = record 空間中的一個(gè)單位立方體 x,y,z: Shortint;end;Tar： a

28、rray1.50 of TPoint; 目標(biāo)形狀TCube = array1.4 of TPoint; 一個(gè)積木Cube: array1.most of TCube; 所有的狀態(tài)分析看到這個(gè)題目，就會(huì)想到搜索。這是一道有一定難度的題目，盲目的搜索是不行的，因?yàn)轭}目中說(shuō)明了每種積木都可以經(jīng)過(guò)翻轉(zhuǎn)和平移，然而，只要得到了平移或翻轉(zhuǎn)后的積木，我們就只需要一個(gè)一個(gè)的往構(gòu)形里面填，直到填滿(mǎn)，這顯然是一個(gè)深度優(yōu)先搜索。然而對(duì)于這道題目來(lái)說(shuō)，除了搜索之外，還有一個(gè)難點(diǎn)，就是生成所有的翻轉(zhuǎn)或平移后的積木狀態(tài)。我們考慮用一個(gè)三員組表示空間中的1*1*1的立方體(單位立方體)，三員組(x,y,z)表示空間(x,y

29、,z)處有一個(gè)單位立方體。這樣我們就有三種數(shù)據(jù)結(jié)構(gòu)：TPoint = record一個(gè)點(diǎn)x,y,z: Shortint; end；TCube = array1.4 of TPoint;一個(gè)積木TBlock = array1.50 of TPoint;給定的三維形狀怎樣生成所有狀態(tài)？首先，題目中指出：可以平移，翻轉(zhuǎn)，但不可以成不可以成鏡像鏡像。如何處理平移？我們只要保存一個(gè)積木中四個(gè)頂點(diǎn)的相對(duì)位置相對(duì)位置，在搜索的時(shí)候自然就可以完成平移，在此我們規(guī)定一個(gè)積木的一個(gè)單位立方體為(0,0,0)，則其余三個(gè)可以用相對(duì)于這個(gè)單位立方體的位置來(lái)表示。如何處理翻轉(zhuǎn)？由于題目規(guī)定不可以成鏡像，所以，我們?cè)谏?/p>

30、所有狀態(tài)時(shí)的翻轉(zhuǎn)過(guò)程中，必成偶數(shù)次偶數(shù)次鏡像(因?yàn)椋撼膳紨?shù)次鏡像等于沒(méi)成偶數(shù)次鏡像等于沒(méi)成鏡像成鏡像)。由于旋轉(zhuǎn)積木很難理解，也有可能會(huì)遺漏一些情況，我們采用的是旋轉(zhuǎn)坐標(biāo)軸旋轉(zhuǎn)坐標(biāo)軸的方法?？梢赃@么理解旋轉(zhuǎn)坐標(biāo)軸法旋轉(zhuǎn)坐標(biāo)軸法：旋轉(zhuǎn)坐標(biāo)軸法旋轉(zhuǎn)坐標(biāo)軸法可以這么理解旋轉(zhuǎn)坐標(biāo)軸法旋轉(zhuǎn)坐標(biāo)軸法：顧名思義，就是要在三維空間中，將坐標(biāo)軸旋轉(zhuǎn)，當(dāng)然，旋轉(zhuǎn)后的坐標(biāo)要兩兩垂直，在滿(mǎn)足這個(gè)條件的情況下，用temp:TCube表示某積木cube Tcube經(jīng)過(guò)某種旋轉(zhuǎn)后所得的狀態(tài)。設(shè)func(temp)表示有幾條坐標(biāo)線(xiàn)(射線(xiàn)射線(xiàn))所在所在直線(xiàn)直線(xiàn)和原來(lái)這條坐標(biāo)線(xiàn)所在直線(xiàn)所在直線(xiàn)的不不重合的?？紤]func(temp

31、)的不同值：設(shè)f(temp)表示在func(temp)的基礎(chǔ)上得到的表示temp性質(zhì)的函數(shù):對(duì)于某一條特定的坐標(biāo)，如果規(guī)定一個(gè)方向?yàn)檎较?，則可以用g(temp)表示旋轉(zhuǎn)后的新坐標(biāo)線(xiàn)中方向和原來(lái)方向不同的條數(shù)。(注：這里的方向并非表示三維空間中的方向，只表示正負(fù)正負(fù))。易得：若f(temp)+g(temp)為偶數(shù)，則temp是符合題意，即成偶數(shù)次鏡像成偶數(shù)次鏡像的。搜索的時(shí)候，另需一個(gè)數(shù)組space:array1.7,1.7,1.7 of byte; spacex,y,z=1表示此處未放, spacex,y,z=0表示放了。procedure search(u,dep,left: intege

32、r);var i: integer;begin if left = 0 then begin 修改;退出 end; 若(left 1) DIV 4 + 1 = min then Exit;分支定界找到一個(gè)space taru,1,taru,2,taru,30的u;tar是目標(biāo)形狀若不存在則退出; repeat 找到一個(gè)可以放置且覆蓋(taru,1,taru,2,taru,3)的積木; 若找到則: begin 放下; search(u+1,dep+1,left-counti);counti是第I個(gè)積木的體積 end; until 找不到;end;分析值得注意的是, 找一個(gè)可放置的積木時(shí),我們不僅

33、要枚舉積木，而且要枚舉點(diǎn)(taru,1,taru,2,taru,3)在積木中的位置。如下面的圖形:我們要枚舉點(diǎn)(taru,1,taru,2,taru,3)在積木中的四中位置情況,然后遞歸搜索，這樣才能夠全面。至此，這道題目可以說(shuō)是得到比較圓滿(mǎn)解決了，按照這種方法便出來(lái)的程序速度是比較快的，能夠?qū)σ话胱笥业臏y(cè)試數(shù)據(jù)。而接下來(lái)我們要做的，就是進(jìn)行優(yōu)化。優(yōu)化這里講的優(yōu)化，主要是針對(duì)搜索時(shí)的一些技巧來(lái)講的。在搜索的過(guò)程中，我們發(fā)現(xiàn)：我們的目的實(shí)際上就是要把一些積木放到構(gòu)形里面去，不妨換個(gè)角度，把一個(gè)構(gòu)形看成由許多單位立方體構(gòu)成的，同樣的，一個(gè)積木也是由許多單位立方體構(gòu)成。我們把這個(gè)構(gòu)形拆開(kāi)承單個(gè)的單位

34、立方體，每次從里面去出成分和某一塊積木陳分相同一些單位立方體。因此，不妨令這些單位立方體是有序的，同樣，積木的描述也是有序的。搜索時(shí)，由小到大由小到大去填充構(gòu)形的某一個(gè)單位立方體，如果輪到填充構(gòu)形中的某一個(gè)單位立方體時(shí)，我們就必須讓它成為某一個(gè)積木描述中最靠前(最最”小小”)的那一部分，因?yàn)槿绻贿@樣，這個(gè)單位立方體就再不可能被覆蓋了。這樣就免去了上面所說(shuō)的確定這個(gè)單位立方體中相對(duì)位置的過(guò)程，效率有很大的提高。然而，我們需要一個(gè)標(biāo)準(zhǔn)來(lái)衡量一個(gè)單位立方體的“大小”，這很簡(jiǎn)單，就先以x為關(guān)鍵字排序；在x相同的前提下，以y為關(guān)鍵字排序；在x,y都相同的前提下，以z為關(guān)鍵字排序。優(yōu)化在程序開(kāi)始時(shí)可以得

35、到一個(gè)最優(yōu)值best=(n 1) DIV 4 + 1;一旦搜索到的解達(dá)到了這個(gè)值就可以中止程序。因?yàn)楦鞣N積木的第一個(gè)單位立方體都是(0,0,0)，保存各種狀態(tài)時(shí)只需用三個(gè)TPoint，雖然這對(duì)于空間存儲(chǔ)來(lái)說(shuō)并不是問(wèn)題。此外,搜索的順序?qū)τ跁r(shí)間效率很重要，在編程當(dāng)中，我們可以發(fā)現(xiàn)，若把較為平直的積木放在cube數(shù)組的前面，這樣，循環(huán)時(shí)先找到的就是較平直的，事實(shí)證明，用這樣的方法，很多的數(shù)據(jù)都有明顯的超時(shí)，這可能是由于平直的積木不利于剪枝而造成的。我們可以同樣考慮將積木按體積從達(dá)到小排序，這樣，即容易出解也利于剪枝。優(yōu)化如下表，給出了某一組數(shù)據(jù)的出解時(shí)間：空間上：有用狀態(tài)數(shù)不是很多，105種，而且

36、目標(biāo)形狀的體積也不是很大，所以空間上是完全承受的了的。時(shí)間上：由于有很多的狀態(tài)是不能被放置的，所以有了上面的分支定界和剪枝，應(yīng)該可以在規(guī)定時(shí)間內(nèi)出解。預(yù)處理程序見(jiàn)目錄下：preparation.pas解題程序見(jiàn)目錄下：block.pas道路n(n=10)個(gè)點(diǎn)的有向完全圖，每條邊都有一個(gè)實(shí)數(shù)權(quán)值，現(xiàn)在我們要找一條長(zhǎng)度為n的路使得路上的邊權(quán)和最接近一個(gè)數(shù)x。注意：每個(gè)點(diǎn)都有自環(huán)。自環(huán)指的是對(duì)于一個(gè)點(diǎn)，存在一條邊，從這個(gè)點(diǎn)出發(fā)，指向這個(gè)點(diǎn)本身。這條路徑允許經(jīng)過(guò)重復(fù)的點(diǎn)和重復(fù)的邊。分析考慮搜索狀態(tài)：將所有的路徑都搜索出來(lái)。狀態(tài)量：當(dāng)n=10時(shí)，狀態(tài)量高達(dá)1010，所以廣搜是不行的。那么考慮進(jìn)行深搜，考

37、慮深搜的剪枝搜索順序（無(wú)關(guān)緊要）可行性剪枝（不行，每條路徑都可行）最優(yōu)性剪枝（有可能，但效果可能不明顯）經(jīng)典剪枝（二分法）這種剪枝方法基于將問(wèn)題縮小規(guī)模的思想。我們可以將一條路徑分兩次搜索，每次搜一半。先搜出所有的長(zhǎng)度為n/2的路徑，并存下來(lái)，當(dāng)做路徑的前半段。用fij數(shù)組存下所有以i結(jié)尾的長(zhǎng)度為n/2的路徑權(quán)值和，并將j這一維按權(quán)值和排序。即fi1表示所有路徑中權(quán)值和最大的， fi2表示權(quán)值和第二大的，以此類(lèi)推。然后搜后半段路徑，每搜出一條路徑，若這條路徑以i開(kāi)頭，權(quán)值和為y，則在fi中二分查找一個(gè)離x-y最近的權(quán)值和，構(gòu)成完整的路徑。Noi2001方程的解數(shù)也是用這個(gè)方法。算符破譯（NOI

38、2000）考古學(xué)發(fā)現(xiàn)，幾千年前古梅文明時(shí)期的數(shù)學(xué)非常的發(fā)達(dá)，他們懂得多位數(shù)的加法和乘法，其表達(dá)式和運(yùn)算規(guī)則等都與現(xiàn)在通常所用通常所用的方式完全相同（如整數(shù)是十進(jìn)制，左邊是高位，最高位不能為零；表達(dá)式為中綴運(yùn)算，先乘后加等），唯一的區(qū)別是其符號(hào)的寫(xiě)法與現(xiàn)在不同。有充分的證據(jù)表明，古梅文明的數(shù)學(xué)文字一共有13個(gè)符號(hào)，與 0,1,2,3,4,5,6,7,8,9,+,*,= 這13個(gè)數(shù)字和符號(hào)（稱(chēng)為現(xiàn)代算符）一一對(duì)應(yīng)。為了便于標(biāo)記，我們用13個(gè)小寫(xiě)英文字母a,b,m代替這些符號(hào)（稱(chēng)為古梅算符）。但是，還沒(méi)有人知道這些古梅算符和現(xiàn)代算符之間的具體對(duì)應(yīng)關(guān)系。在一個(gè)石壁上，考古學(xué)家發(fā)現(xiàn)了一組用古梅算符表示的

39、等式，根據(jù)推斷，每行有且僅有一個(gè)等號(hào)，等號(hào)左右兩邊為運(yùn)算表達(dá)式（只含有數(shù)字和符號(hào)），并且等號(hào)兩邊的計(jì)算結(jié)果相等。假設(shè)這組等式是成立的，請(qǐng)編程序破譯古梅算符和現(xiàn)代算符之間的對(duì)應(yīng)關(guān)系。 輸入文件輸入文件的第一行為等式的個(gè)數(shù)N（1=N=1000），以下N行每行為一個(gè)等式。每個(gè)等式的長(zhǎng)度為5個(gè)字符到11個(gè)字符。輸出文件如果不存在對(duì)應(yīng)關(guān)系能夠滿(mǎn)足這組等式，輸出“noway”和一個(gè)換行/回車(chē)符。如果有對(duì)應(yīng)關(guān)系能夠滿(mǎn)足這組等式，輸出所有能夠確定的古梅算符和現(xiàn)代算符的對(duì)應(yīng)關(guān)系。每一行有兩個(gè)字符，其中第一個(gè)字符是古梅算符，第二個(gè)字符是對(duì)應(yīng)的現(xiàn)代算符。輸出按照字典順序排序。樣例：輸入： 輸出：2 a6abcdec b*cdefe d= f+樣例說(shuō)明:在上例中，可能對(duì)應(yīng)的現(xiàn)代表達(dá)式為6*2=12，2=1+1，6*4=24，4=2+2，6*8=48，8=4+4。可見(jiàn)，能夠確定的對(duì)應(yīng)關(guān)系只有a對(duì)應(yīng)6，b對(duì)應(yīng)*，d對(duì)應(yīng)=，f對(duì)應(yīng)+，應(yīng)該輸出；而c,e雖然能夠找到對(duì)應(yīng)的現(xiàn)代算符使得等式成立，但沒(méi)有唯