黃曉愉深度優(yōu)先搜索問題的優(yōu)化技巧

1、2006年全國信息學冬令營講座信息學競賽中搜索問題的常見優(yōu)化技巧重慶一中黃曉愉【摘要】結合例題分析歸納了信息學競賽中解決搜索問題所常用的思考方法與解題方法，從深度 優(yōu)先搜索和廣度優(yōu)先搜索兩個方面探討了提高程序效率的適用技巧。【關鍵詞】1信息學；2搜索順序；3搜索對象；4 Hash表5剪枝。在信息學競賽中解決搜索問題通常采用兩種方法進行，即：深度優(yōu)先搜索和廣度 優(yōu)先搜索。一、深度優(yōu)先搜索的優(yōu)化技巧我們在做題的時候，經常遇到這類題目一一給出約束條件，求一種滿足約束條件 的方案，這類問題我們叫它“約束滿足”問題。對于約束滿足問題，我們通?？梢詮?搜索的順序和搜索的對象入手，進而提高程序的效率。搜索的

2、順序及對象：在解決約束滿足問題的時候，題目給出的約束條件越強，對于搜索中的剪枝就越 有利。之所以深度優(yōu)先搜索的效率在很大程度上優(yōu)于窮舉，就是因為它在搜索過程中 很好的利用了題目中的約束條件進行剪枝，達到提高程序效率的目的。顯然，在同樣的一棵搜索樹中，越在接近根接點的位置利用約束條件剪枝效果就 越好。如何在搜索中最大化的利用題目的約束條件為我們提供剪枝的依據，是提高深 度優(yōu)先搜索效率的一個很重要的地方。而不同的搜索順序和搜索對象就直接影響到我 們對于題目約束條件的運用。下面，我們就從搜索的順序和搜索的對象兩方面來探討一下不同的方法對程序效 率的影響。（1搜索順序的選擇：我們先來看一道比較簡單的題

3、目：（zju1937）已知一個數列a0,a1am 其中a0 = 1 am = n a0 < al < a2 < . < am-1 < am對于每個 k(1<=k<=m),ak=ai+aj (0 <= i, j <= k-1)，這里 i 與 j 可以相等。現給定n的值，要求m的最小值(并不要求輸出)，及這個數列的值(可能存在多 個數列,只輸出任一個滿足條件的就可以了 )。分析 由于ak=a+aj(0<=i,j<k),所以我們在搜索的過程中可以采用由小到大搜索數 列的每一項的搜索順序進行試算。 在一般搜索的時候我們習慣于從小到大依次

4、搜索每 個數的取值，但是在這到題目中按照這樣的順序搜索編程運算其結果(效率)十分不 理想：N102030405060708090100200300400500用時0.030.010.030.050.200.341.801.808.9110.1ToolongToolongToolongToolong由于題目要求的是m的最小值，也就是需要我們盡快得到數 n,所以每次構造的 數應當是盡可能大的數，根據題目的這個特性，我們將搜索順序改為從大到小搜索每 個數，新程序的效率如下：N102030405060708090100200300400500用時0.010.010.010.010.010.010.03

5、0.010.030.030.131.481.522.88顯然，后一種搜索順序得到的程序效率大大地優(yōu)于第一種搜索順序得到的程序。當然，這道題還有很大的優(yōu)化余地，但是搜索順序這種思想在搜索的題目中是廣泛運用的。也許大家會覺得這種單一的運用搜索順序來優(yōu)化程序的方法很普通，但是這種看似簡單的方法在考試中出現得也不少，例如1012000中的BLOCK只要將木塊從大到小經過旋轉和反轉后，依次放入進行搜索，對于比賽中的數據就可以得到滿分。最近的一次出現是NOI2005中的智慧珠，同樣的只是將珠子從大到小進行搜索，不加任何其他剪枝就可以在比賽中獲得 90分。可見，選擇合適的搜索順序對于提高程序的效率是編程設計

6、最有效的技巧之一，運用良好的搜索順序來對搜索題目進行優(yōu)化是一個性價比很高的算法。（2）搜索對象的選擇：讓我們再來看看下面一道題：（USAC9 weight）已知原數列ai, a2,an中前1項，前2項，前3項,前 n項的和，以及后1項后2項,后3項,后n項的和，但是所有的數據都已經被打亂了順序，還知道數列中的數存在集合S中，求原數列。當存在多組可能數列的時候求左邊的數最小的數列。 其中 nv=1000,S 1.50010例如，假如原數列為1 1 5 2 5，S=1，14 5 712 13 14)1 =15 = 52 =1+17 = 2+57 =1+1+512 = 5+2+59 =1+1+5+2

7、13 = 1+5+2+514=1+1+5+2+514 =1+1+5+2+52, 4, 5那么知道的值就是（1 2 7 9分析 因為題目中的S 1.500，最壞的情況下每個數可以取到的值有 500種，從 數學方面很難找到有較好方法予以解決，而采用搜索方法卻是一種很好的解決辦法， 根據數列從左往右依次搜索原數列每個數可能的值，然后與所知道的值進行比較。這 樣，我們得到了一個最簡單的 搜索方法Ao但是搜索方法A的這個算法最壞的情況下擴展的節(jié)點為5001000,運算速度太慢了。在這個算法中，我們對數列中的每個數分別進行了500次搜索，由此導致了搜索量如此之大。如何有效的減少搜索量是提高本題算法效率的關

8、鍵。而前面提到的運用搜索順序的方法在本題中由于規(guī)定了左邊的數最小而無法運用。讓我們換個角度對這個問題進行思考：搜索方法B:回過頭來看看題目提供給我們的約束條件，我們用S表示前I項的和，用Ti表示后I項的和。根據題目，我們得到的數據應該是數列中的 Si,S2,Ss,Sn，以及Ti,T2,T3,Tn。其中的任意Si+1-Si和Ti+1-Ti都屬于集合S。另一個比較容易發(fā)現的約束條件是對于任 意的I，有Sn=Tn=Si+Tn-l。同樣的，在搜索的過程中最大化這些約束條件是提高程 序效率的關鍵。那么當我們任意從已知的數據中取出兩個數的時候，只會出現兩種情況：1、兩個數同屬于Si,或者TiSISiSjS

9、r2、兩數分別屬于Ti和SiS1SiTjTI當兩數同屬于Si或者Ti時，兩個數之差，就是圖中Sj-Si那一段，而當j=l+1時， Sj-Si必然屬于題目給出的集合S。由此，當每次得到一個數 Si或者Ti時，如果我們 已知Si-i或者Ti-i，便能夠判斷出此時的S或者Ti是否合法。所以我們在搜索中盡可 能利用S-i和Ti-i推得Si和Ti的可能，便能盡可能利用題目的約束條件。因為題目的約束條件集中在Si和Ti中，我們改變搜索的對象，不再搜索原數列中每個數的值，而是搜索給出的數中出現在Si或者Ti中的位置。又由于約束條件中得出的S+i與Si的約束關系，提示我們在搜索中按照 S中i遞增或者遞減的順序

10、進行 搜索。例如，對于數據組：i i 5 2 5 ，由它得到的值為i 2 7 9 i4 5 7 i2 i3 i4排序后為:1 2 5 7 7 9 12 13 14 14由于最大的兩個數為所有數的和，在搜索中不用考慮它們，去掉14:1 2 5 7 7 9 12 13觀察發(fā)現，數列中的最小數1,只可能出現在所求數列的頭部或者尾部。再假設 1的位置已經得到了，去掉它以后，我們再觀察剩下的數中最小的數2,顯然也只可能在當前狀態(tài)的頭部或者尾部加上一個數得到2。這樣，每搜索一個數，都只會將它放在頭部和尾部，也就是放入 S中或者Ti中。推而廣之，我們由小到大對排序的數進行搜索，判斷每個數是出現在原數列頭部

11、還是尾部。此時我們由原數列的兩頭向中間搜索，而不是先前的從一頭搜向另一頭。 由之前的分析已經知道，每個數只可能屬于Si和Ti中。當我們已經搜索出原數列的S1,S2S i和丁訂2T j,此時對于正在搜索的數K,只可能有兩種存在的可能：Si+1和Tj+1， 分別依次搜索這兩個可能，即判斷 K-Si和K-Tj是否屬于已知集合S。并且在每搜索 出一個數K的時候，我們將排序后的數列中Sn-k去掉。這樣，當K-Si（Ti）不屬于集合S或者Sn-k不存在與排序后的數列時，就回溯。這樣得到的算法在最壞情況下擴展的節(jié)點為 21000（實際中遠遠小于這個數），并且 由于在搜索過程中充分利用了題目約束條件，其程序運

12、行結果如下：在這道題目中，原始的搜索方法搜索量巨大，我們通過分析，選擇適當的搜索對 象,在搜索量減少的同時充分利用了題目的約束條件，成為了程序的一個有利的剪枝，使題目得到較好的解決。、廣度優(yōu)先搜索的優(yōu)化技巧相對于深度優(yōu)先搜索的另外一類題目一一給出起始和目標狀態(tài)，以及狀態(tài)轉移的規(guī)則，要求找到一條到達目標狀態(tài)的的路徑或者方法。這類問題我們叫它路徑尋找問 題（例如走迷宮問題）。解決這類問題最有效的手段是選取合適的構造Hash表的方法。Hash表的一般構造方法有：狀態(tài)壓縮運用2進制來記錄狀態(tài)直接取余法-選取一個素數M作為除數。平方取中法-計算關鍵值平方，再取中間r位形成一個大小為2r的表。 折疊法 把

13、所有字符的ASCII碼加起來。路徑尋找問題中，經常會遇到走回頭路的問題，所以在搜索的過程中都必須做一件事，就是判重。判重是決定程序效率的關鍵，而如何構造一個優(yōu)秀的Hash表決定著這一切。一個好的Hash函數可以很大程度上提高程序的整體時間效率和空間效率。(zju1301):黑先生新買了一棟別墅，可是里面的電燈線路的連接是很混亂的(每個房間的開關可能控制其他房間，房間數=10)，有一天晚上他回家時發(fā)現所有的燈(除了他出發(fā) 的房間)都是關閉的，而他想回臥室去休息?？墒呛懿恍遥峙潞?，因此他不會 走入任何關著燈的房間，于是請你幫他找出一條路使他既能回到臥室又能關閉除臥室 以外的所有燈。如果同時有

14、好幾條路線的話，請輸出最短的路線。分析 這是一道比較簡單的搜索題目，題目要求是一條路徑，所以我們用廣度優(yōu)先搜 索來解決。廣度優(yōu)先搜索不能避免的是重復狀態(tài)，而用循環(huán)判斷重復是得不償失的， 在狀態(tài)多的情況下，循環(huán)法甚至比深度優(yōu)先搜索的效率更低，而且低得多。而題目的 難點在于Hash表的構造，經過分析發(fā)現，對于狀態(tài)有影響的便是房間內電燈的開關 與否，還有當時所在的房間。由于電燈只有開和關兩種情況，我們考慮用2進制來儲 存狀態(tài)，也就是大家熟悉的狀態(tài)壓縮。將每個房間中電燈的狀態(tài)用0和1來表示，然后將10個房間的狀態(tài)排列起來就 成了 1000100101這樣的形式。然后將他轉換成10進制(10001001

15、01)2=(549)1。，這樣一來就可以為唯一的表示出一個電燈開關的狀態(tài)，再用一個數記錄下黑先生當時所在的房間，就成功地構造出了所需的 Hash表?？偣驳臓顟B(tài)數為210*10=10240。同時，在搜索中可以用位運算來判斷某個房間的狀態(tài)，使得 Hash表的填充和查 找變得簡單。例如，假設當前狀態(tài)為 K,現在要判斷第I個房間的狀態(tài)。只需(2i-1 and K)是否為0就行了。這樣一來，這道題就已經解決了。遠，在此基礎上使AB盡快到達終點。如圖為N=10時的一種情況分析：本題是求路徑的一道題，所以是一道很明顯的廣度優(yōu)先搜索題目，題目的條件很多：首先是要AB都到達終點，然后是要路徑中 AB離得盡可能的

16、遠，同時 AB要盡 快到達。我們首先嘗試用Hash表將所有的信息存下，然后進行搜索，我首先想到了兩種 構造Hash表的方法：1、用Hashx1,y1,x2,y2,t 表示經過了 t個時間點，A到達坐標(x1,y1) ，B 到達(x2,y2)，它們在途中的最近距離。2、用 Hashx1,y1,x2,y2,k 當 A到達坐標(x1,y1) ，B 到達坐標(x2,y2)，它 們在途中的最近距離為k時的最少時間。這兩種方法構造方法共同的特點是Hash表中儲存了大量的信息，并且在編程實現中比較困難。由于大量的條件在Hash表中堆積，我們嘗試將其中的一個條件從 Hash表中去掉， 用其他的方法來分擔。假設

17、我們已經知道了兩人在途中的最近距離，那么剩下的將會簡單許多。但是怎 樣才能知道兩人在途中的最短距離呢？我們想到了二分。在兩個人在地圖上的距離差最多只可能有304 = 810000種可能，如果我們采用2分法，最多只需要log2810000<20次，然后在用廣度優(yōu)先搜索來解決剩下的問題，那么 最壞的情況下擴展的節(jié)點數為 20*304=16200000。完全可以在規(guī)定的時間內得出結果。考慮到在AB移動的過程中，同一個狀態(tài)（x1,y1,x2,y2）不可能出現兩次，那么可 以考慮直接用Hash表將狀態(tài)（x1,y1,x2,y2）的情況存下，于是Hash表中應該儲存下A 到達坐標（x1,y1） ，B到

18、達坐標（x2,y2），它們途中的最近距離并且在此基礎上的最短 時間。小結Hash表是非常重要的廣度優(yōu)先搜索優(yōu)化方式之一，它能夠把搜索算法的效率從 大指數級提高到小指數級、多項式級甚至常數級。三、深度優(yōu)先搜索和廣度優(yōu)先搜索的有力工具-剪枝USACO-Cryptcowgraphy（解密牛語）農民Brown和John的牛們計劃協同逃出它們各自的農場。它們設計了一種加密 方法用來保護它們的通訊不被他人知道。如果一頭牛有信息要加密， 比如"International Olympiad in Informatics"，它會隨機 地把C, O, W三個字母插到到信息中（其中 C在O前面，

19、O在W前面），然后它把C 與O之間的文字和O與W之間的文字的位置換過來。這里是兩個例子：Intern ati onal Olympiad in In formatics->C nOI Wternatio nal Olympiad in In formaticsIntern ati onal Olympiad in In formatics-Intern ati onal Cin In formaticsOOlympiad W 為了使解密更復雜，牛們會在一條消息里多次采用這個加密方法（把上次加密的 結果再進行加密）。一天夜里，John的牛們收到了一條經過多次加密的信息。請你寫 一個程序判斷它是不是這條信息經過加密（或沒有加密）而得到的：Begi n the Escape executi on at the Break of Daw n分析 基于密碼編譯規(guī)則，我們很容易地可以想出一個非常簡單的dfs方法，當然，那是明顯要超時的，而分析題目我們可以發(fā)現，題目要求的是一種得到信息的加密方 法，也就是求的一種加密的路徑。于是我們不得不采用寬度優(yōu)先搜索算法。對于Hash表的構造方法，可以采用 ELFhash函數或者SDBMhash參見05年李羽 修論文）。這里跳過。題目規(guī)定加密信息不超過75個字符，而原始的信息一共有47個字符，那么按照