算法合集之《信息學(xué)競賽中搜索問題的常見優(yōu)化技巧》

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

2、時候，題目給出的約束條件越強(qiáng)，對于搜索中的剪枝就越 有利。之所以深度優(yōu)先搜索的效率在很大程度上優(yōu)于窮舉，就是因?yàn)樗谒阉鬟^程中 很好的利用了題目中的約束條件進(jìn)行剪枝，達(dá)到提高程序效率的目的。顯然，在同樣的一棵搜索樹中，越在接近根接點(diǎn)的位置利用約束條件剪枝效果就 越好。如何在搜索中最大化的利用題目的約束條件為我們提供剪枝的依據(jù)，是提高深 度優(yōu)先搜索效率的一個很重要的地方。而不同的搜索順序和搜索對象就直接影響到我 們對于題目約束條件的運(yùn)用。下面，我們就從搜索的順序和搜索的對象兩方面來探討一下不同的方法對程序效 率的影響。(1)搜索順序的選擇：我們先來看一道比較簡單的題目：(zju1937)已知一個

3、數(shù)列a0,a1 am 其中a0=1am=na0a1a2.am-1am對于每個 k(1=k=m),ak=ai+aj(0=i,j=k-1),這里 i 與 j 可以相等?，F(xiàn)給定n的值，要求m的最小值(并不要求輸出)，及這個數(shù)列的值(可能存在多 個數(shù)列，只輸出任一個滿足條件的就可以了 )。分析 由于ak=a+a(0=i,jk),所以我們在搜索的過程中可以采用由小到大搜索數(shù)列的每一項(xiàng)的搜索順序進(jìn)行試算。在一般搜索的時候我們習(xí)慣于從小到大依次搜索每個數(shù)的取值，但是在這到題目中按照這樣的順序搜索編程運(yùn)算其結(jié)果(效率)十分不 理想：N102030405060708090100200300400500用時0.0

4、30.010.030.050.200.341.801.808.9110.1ToolongToolongToolongToolong由于題目要求的是m的最小值，也就是需要我們盡快得到數(shù) n,所以每次構(gòu)造的 數(shù)應(yīng)當(dāng)是盡可能大的數(shù)，根據(jù)題目的這個特性，我們將搜索順序改為從大到小搜索每 個數(shù)，新程序的效率如下：N102030405060708090100200300400500用時0.010.010.010.010.010.010.030.010.030.030.131.481.522.88顯然，后一種搜索順序得到的程序效率大大地優(yōu)于第一種搜索順序得到的程序。當(dāng)然，這道題還有很大的優(yōu)化余地，但是搜索順

5、序這種思想在搜索的題目中是廣 泛運(yùn)用的。也許大家會覺得這種單一的運(yùn)用搜索順序來優(yōu)化程序的方法很普通，但是 這種看似簡單的方法在考試中出現(xiàn)得也不少，例如IOI2000中的BLOCK只要將木塊從大到小經(jīng)過旋轉(zhuǎn)和反轉(zhuǎn)后，依次放入進(jìn)行搜索，對于比賽中的數(shù)據(jù)就可以得到滿分最近的一次出現(xiàn)是NOI2005中的智慧珠，同樣的只是將珠子從大到小進(jìn)行搜索，不加 任何其他剪枝就可以在比賽中獲得 90分。可見，選擇合適的搜索順序?qū)τ谔岣叱绦虻男适蔷幊淘O(shè)計最有效的技巧之一， 運(yùn)用良好的搜索順序來對搜索題目進(jìn)行優(yōu)化是一個性價比很高的算法。(2)搜索對象的選擇：讓我們再來看看下面一道題：(USACO- weight)已知

6、原數(shù)列ai, a2an中前1項(xiàng)，前2項(xiàng)，前3項(xiàng)前n項(xiàng)的和,以及后1項(xiàng),后2項(xiàng)，后3項(xiàng)后n項(xiàng)的和，但是所有的數(shù)據(jù)都已經(jīng)被打亂了順序，還知道數(shù)列 中的數(shù)存在集合S中，求原數(shù)列。當(dāng)存在多組可能數(shù)列的時候求左邊的數(shù)最小的數(shù)列。 其中 n=1000,S 1.500例如，假如原數(shù)列為11525, S=1, 2, 4, 5那么知道的值就是(12791457121314)1=15=52=1+17=2+57=1+1+512=5+2+59=1+1+5+213=1+5+2+514=1+1+5+2+514=1+1+5+2+5分析 因?yàn)轭}目中的SC 1.500，最壞的情況下每個數(shù)可以取到的值有 500種，從 數(shù)學(xué)方面很

7、難找到有較好方法予以解決，而采用搜索方法卻是一種很好的解決辦法， 根據(jù)數(shù)列從左往右依次搜索原數(shù)列每個數(shù)可能的值，然后與所知道的值進(jìn)行比較。這 樣，我們得到了一個最簡單的 搜索方法Ao但是搜索方法A的這個算法最壞的情況下擴(kuò)展的節(jié)點(diǎn)為 5001000,運(yùn)算速度太慢了。在這個算法中，我們對數(shù)列中的每個數(shù)分別進(jìn)行了500次搜索，由此導(dǎo)致了搜索量如此之大。如何有效的減少搜索量是提高本題算法效率的關(guān)鍵。而前面提到的運(yùn)用 搜索順序的方法在本題中由于規(guī)定了左邊的數(shù)最小而無法運(yùn)用。讓我們換個角度對這個問題進(jìn)行思考：搜索方法B:回過頭來看看題目提供給我們的約束條件，我們用 S表示前I項(xiàng)的 和，用Ti表小后I項(xiàng)的和

8、。根據(jù)題目，我們得到的數(shù)據(jù)應(yīng)該是數(shù)列中的 Sl,S2,S3Sn,以及Ti,T2,T3Tn。 其中的任意Si+1-Si和Ti+1-Ti都屬于集合S。另一個比較容易發(fā)現(xiàn)的約束條件是對于任 意的I,有Sn=Tn=Si+Tn-I。同樣的，在搜索的過程中最大化這些約束條件是提高程 序效率的關(guān)鍵。那么當(dāng)我們?nèi)我鈴囊阎臄?shù)據(jù)中取出兩個數(shù)的時候，只會出現(xiàn)兩種情況：1、兩個數(shù)同屬于Si,或者Ti2、兩數(shù)分別屬于Ti和Si。51SiTjTI當(dāng)兩數(shù)同屬于Si或者不時，兩個數(shù)之差，就是圖中Sj-Si那一段，而當(dāng)j=I+1時， Sj-Si必然屬于題目給出的集合S。由此，當(dāng)每次得到一個數(shù)Si或者Ti時，如果我們已知Si-

9、i或者Ti-i,便能夠判斷出此時的Si或者Ti是否合法。所以我們在搜索中盡可 能利用S-i和Ti-i推得Si和Ti的可能，便能盡可能利用題目的約束條件。因?yàn)轭}目的約束條件集中在 Si和Ti中，我們改變搜索的對象，不再搜索原數(shù)列 中每個數(shù)的值，而是搜索給出的數(shù)中出現(xiàn)在Si或者Ti中的位置。又由于約束條件中得出的S+i與Si的約束關(guān)系，提示我們在搜索中按照 S中i遞增或者遞減的順序進(jìn)行 搜索。例如，對于數(shù)據(jù)組：ii525,由它得到的值為i279i457i2i3i4排序后為：i25779i2i3i4i4 由于最大的兩個數(shù)為所有數(shù)的和，在搜索中不用考慮它們，去掉 14: 1257791213觀察發(fā)現(xiàn)，

10、數(shù)列中的最小數(shù)1,只可能出現(xiàn)在所求數(shù)列的頭部或者尾部。再假設(shè) 1的位置已經(jīng)得到了，去掉它以后，我們再觀察剩下的數(shù)中最小的數(shù)2,顯然也只可能在當(dāng)前狀態(tài)的頭部或者尾部加上一個數(shù)得到2。這樣，每搜索一個數(shù)，都只會將它放在頭部和尾部，也就是放入 S中或者Ti中。推而廣之，我們由小到大對排序的數(shù)進(jìn)行搜索，判斷每個數(shù)是出現(xiàn)在原數(shù)列頭部 還是尾部。此時我們由原數(shù)列的兩頭向中間搜索，而不是先前的從一頭搜向另一頭。 由之前的分析已經(jīng)知道，每個數(shù)只可能屬于Si和Ti中。當(dāng)我們已經(jīng)搜索出原數(shù)列的S1,S23 S i和T1,T2丁 j,此時對于正在搜索的數(shù)K,只可能有兩種存在的可能：Si+1和Tj+1, 分別依次搜索

11、這兩個可能，即判斷 K-Si和K-Tj是否屬于已知集合S。并且在每搜索 出一個數(shù)K的時候，我們將排序后的數(shù)列中Sn-k去掉。這樣，當(dāng)K-Si（Ti）不屬于集合S或者Sn-k不存在與排序后的數(shù)列時，就回溯。這樣得到的算法在最壞情況下擴(kuò)展的節(jié)點(diǎn)為 21000（實(shí)際中遠(yuǎn)遠(yuǎn)小于這個數(shù)），并且 由于在搜索過程中充分利用了題目約束條件，其程序運(yùn)行結(jié)果如下：在這道題目中，原始的搜索方法搜索量巨大，我們通過分析，選擇適當(dāng)?shù)乃阉鲗?象，在搜索量減少的同時充分利用了題目的約束條件，成為了程序的一個有利的剪枝，使題目得到較好的解決。二、廣度優(yōu)先搜索的優(yōu)化技巧相對于深度優(yōu)先搜索的另外一類題目一一給出起始和目標(biāo)狀態(tài)，以

12、及狀態(tài)轉(zhuǎn)移的規(guī)則，要求找到一條到達(dá)目標(biāo)狀態(tài)的的路徑或者方法。這類問題我們叫它路徑尋找問 題（例如走迷宮問題）。解決這類問題最有效的手段是選取合適的構(gòu)造Hash表的方法。Hash表的一般構(gòu)造方法有：狀態(tài)壓縮運(yùn)用2進(jìn)制來記錄狀態(tài)。選取一個素數(shù)M作為除數(shù)直接取余法平方取中法-計算關(guān)鍵值平方，再取中間r位形成一個大小為2r的表。折疊法 把所有字符的ASCII碼加起來。路徑尋找問題中，經(jīng)常會遇到走回頭路的問題，所以在搜索的過程中都必須做一 件事，就是判重。判重是決定程序效率的關(guān)鍵，而如何構(gòu)造一個優(yōu)秀的Hash表決定著這一切。一個好的Hash函數(shù)可以很大程度上提高程序的整體時間效率和空間效率。(zju13

13、01):黑先生新買了一棟別墅，可是里面的電燈線路的連接是很混亂的(每個房間的開關(guān)可能控制其他房間，房間數(shù)二10),有一天晚上他回家時發(fā)現(xiàn)所有的燈(除了他出發(fā) 的房間)都是關(guān)閉的，而他想回臥室去休息?？墒呛懿恍遥峙潞?，因此他不會 走入任何關(guān)著燈的房間，于是請你幫他找出一條路使他既能回到臥室又能關(guān)閉除臥室 以外的所有燈。如果同時有好幾條路線的話，請輸出最短的路線。分析 這是一道比較簡單的搜索題目，題目要求是一條路徑，所以我們用廣度優(yōu)先搜 索來解決。廣度優(yōu)先搜索不能避免的是重復(fù)狀態(tài)，而用循環(huán)判斷重復(fù)是得不償失的， 在狀態(tài)多的情況下，循環(huán)法甚至比深度優(yōu)先搜索的效率更低，而且低得多。而題目的 難點(diǎn)

14、在于Hash表的構(gòu)造，經(jīng)過分析發(fā)現(xiàn)，對于狀態(tài)有影響的便是房間內(nèi)電燈的開關(guān) 與否，還有當(dāng)時所在的房間。由于電燈只有開和關(guān)兩種情況，我們考慮用2進(jìn)制來儲 存狀態(tài)，也就是大家熟悉的狀態(tài)壓縮。將每個房間中電燈的狀態(tài)用0和1來表示，然后將10個房間的狀態(tài)排列起來就 成了 1000100101這樣的形式。然后將他轉(zhuǎn)換成 10進(jìn)制(1000100101)2=(549)1。，這樣 一來就可以為唯一的表示出一個電燈開關(guān)的狀態(tài)，再用一個數(shù)記錄下黑先生當(dāng)時所在的房間，就成功地構(gòu)造出了所需的 Hash表?？偣驳臓顟B(tài)數(shù)為210*10=10240。同時，在搜索中可以用位運(yùn)算來判斷某個房間的狀態(tài)，使得 Hash表的填充和查

15、 找變得簡單。例如，假設(shè)當(dāng)前狀態(tài)為K,現(xiàn)在要判斷第I個房間的狀態(tài)。只需(2i-1andK) 是否為0就行了。這樣一來，這道題就已經(jīng)解決了。分別的起點(diǎn)和終點(diǎn)。求出一條使 AB到達(dá)終點(diǎn)的路徑，并且在途中 AB間最近的距離最 遠(yuǎn)，在此基礎(chǔ)上使AB盡快到達(dá)終點(diǎn)。如圖為N=10時的一種情況。分析：本題是求路徑的一道題，所以是一道很明顯的廣度優(yōu)先搜索題目，題目的條件很多：首先是要AB都到達(dá)終點(diǎn)，然后是要路徑中 AB離得盡可能的遠(yuǎn)，同時 AB要盡 快到達(dá)。我們首先嘗試用Hash表將所有的信息存下，然后進(jìn)行搜索，我首先想到了兩種 構(gòu)造Hash表的方法：1、 用Hashx1,y1,x2,y2,t表示經(jīng)過了 t個

16、時間點(diǎn)，A到達(dá)坐標(biāo)(x1,y1) , B至ij達(dá)(x2,y2),它們在途中的最近距離。2、 用 Hashx1,y1,x2,y2,k 當(dāng) A到達(dá)坐標(biāo)(x1,y1) , B 到達(dá)坐標(biāo)(x2,y2),它 們在途中的最近距離為k時的最少時間。這兩種方法構(gòu)造方法共同的特點(diǎn)是 Hash表中儲存了大量的信息，并且在編程實(shí) 現(xiàn)中比較困難。由于大量的條件在Hash表中堆積，我們嘗試將其中的一個條件從 Hash表中去掉， 用其他的方法來分擔(dān)。假設(shè)我們已經(jīng)知道了兩人在途中的最近距離，那么剩下的將會簡單許多。但是怎樣才能知道兩人在途中的最短距離呢？我們想到了二分。在兩個人在地圖上的距離差最多只可能有304 = 810

17、000種可能，如果我們采用2分法，最多只需要10g2810000CnOIWternationalOlympiadinInformaticsInternationalOlympiadinInformatics-InternationalCin InformaticsOOlympiadW為了使解密更復(fù)雜，牛們會在一條消息里多次采用這個加密方法（把上次加密的 結(jié)果再進(jìn)行加密）。一天夜里，John的牛們收到了一條經(jīng)過多次加密的信息。請你寫 一個程序判斷它是不是這條信息經(jīng)過加密（或沒有加密）而得到的：BegintheEscapeexecutionattheBreakofDawn分析基于密碼編譯規(guī)則，我們

18、很容易地可以想出一個非常簡單的dfs方法，當(dāng)然，那是明顯要超時的，而分析題目我們可以發(fā)現(xiàn)，題目要求的是一種得到信息的加密方法，也就是求的一種加密的路徑。于是我們不得不采用寬度優(yōu)先搜索算法。對于Hash表的構(gòu)造方法，可以采用 ELFhash函數(shù)或者SDBMhas唯見05年李羽 修論文）。這里跳過。題目規(guī)定加密信息不超過75個字符，而原始的信息一共有47個字符，那么按照 正規(guī)的方式在信息中最多可能加入 9組C ,0?符W如果使用原始的算法進(jìn)行搜 索，將最多擴(kuò)展（9!）3個接點(diǎn)，大大超過了時間的允許，所以剪枝是必要的行為。題目已經(jīng)將原始的信息提供給了我們， 所以如何利用好已知的信息對搜索進(jìn)行剪 枝將直接影響程序的效率。1、密文的每次加密都會加入C,。三個W母，所以輸入的密文長度必須是 47+3n,這樣可以迅速的排除一些數(shù)據(jù)。2、已知密文中的每個字符的個數(shù)除了 C,處必W都是固定的，而且C,。三下W符的個數(shù)也必定在原始信息的基礎(chǔ)上增加了（n-47）/3 （n為輸入信息長度）。3、原文中出現(xiàn)的C ,。均為W寫，那么在加密后的信息里面，連續(xù)的C , O