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

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

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

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

4、+1,Ri+1,Hi+1,Vi+1,Si+1)滿足: （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）是否當前面積最小若上述條件成立，則保留當前最優(yōu)值，否則繼續(xù)做下一層蛋糕，若重做蛋糕基本算法Search (i, Ri , Hi , Si , Vi) 對每層蛋糕進行搜索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）因為知道余下的蛋糕體積）因為知道余下的蛋糕體積, ,因此可以估算一下余下側(cè)面積因此可以估算一下余下側(cè)面積, , 這樣我們可以就加入如下剪枝條件這樣我們可以就加入如下剪枝條件: : if if 當前的表面積當前的表面積 + + 余下的側(cè)面積余下的側(cè)面積 當前最優(yōu)值當前最優(yōu)值 then exitthen exit 設(shè)已經(jīng)做了設(shè)已經(jīng)做了i i層蛋糕層蛋糕, ,則還需做則還需做m-im-i層層, , S Si i：為第：為第i i層蛋糕的側(cè)面積層蛋糕的側(cè)面積, , FS FSi i：余下的側(cè)面積：余下的側(cè)面積, ,怎么求

7、怎么求FSFSi i ? ? 因為因為: : 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 當前最優(yōu)值當前最優(yōu)值 then exit優(yōu)化？(2)如果剩下的蛋糕材料太少，不能保證做到m層,那么沒有必要繼續(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當前最優(yōu)值當前最優(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. 計算計算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 V

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

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

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

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

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

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

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

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

18、前這張軟盤的剩余空間；LeftModCap：Extended 剩余軟盤的總字節(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)增加一張軟盤，繼續(xù)搜索 else SENSOR(Order + 1,Num,Free - ModCapI,LeftM

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

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

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

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

23、果也都是不錯的。接下來看一道例題。拓撲排序描述：再一個軟盤中的組件，如果沒有制約關(guān)系，那么調(diào)換其順序，又將變?yōu)榱硪环N方案（此軟件有n個組件，就有N！種重復情況），而如果很多軟盤都如此，將有許多重復情況，時間復雜度將聚增。如何避免這些情況呢？實現(xiàn)：先將所有的組件按拓撲排序（如由多個拓撲排序，任意一個），然后將原順序變?yōu)橥負湫蛄校ò赐負渑判蚝蟮男蛄校?，然后每張軟盤內(nèi)部組件編號（拓撲排序后的編號）的順序規(guī)定為增序，這樣即避免了重復，又不會漏解，一舉兩得。拓撲排序證明：假設(shè)有時必須亂序（亂序：不是增序）才可得到最優(yōu)解。因為亂序可以得到最優(yōu)，那么將這些組件按增序也同樣可以得到最優(yōu)（因為將順序變?yōu)樵鲂蚝螅?/p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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