談搜索算法的剪枝優(yōu)化

1、談搜索算法的剪枝優(yōu)化許晉炫 【摘要】本文討論了搜索算法中“剪枝”這一常見的優(yōu)化技巧。首先由回溯法解決迷宮問題展開論述，介紹了什么是剪枝；而后分析剪枝的三個(gè)原則棗正確、準(zhǔn)確、高效，并分別就剪枝的兩種思路：可行性剪枝及最優(yōu)性剪枝，結(jié)合例題作進(jìn)一步的闡述；最后對(duì)剪枝優(yōu)化方法進(jìn)行了一些總結(jié)?！娟P(guān)鍵字】搜索、優(yōu)化、剪枝、時(shí)間復(fù)雜度引 論在競(jìng)賽中，我們有時(shí)會(huì)碰到一些題目，它們既不能通過建立數(shù)學(xué)模型解決，又沒有現(xiàn)成算法可以套用，或者非遍歷所有狀況才可以得出正確結(jié)果。這時(shí)，我們就必須采用搜索算法來解決問題。     搜索算法按搜索的方式分有兩類，一類是深度優(yōu)先搜索，一類

2、是廣度優(yōu)先搜索。我們知道，深度搜索編程簡(jiǎn)單，程序簡(jiǎn)潔易懂，空間需求也比較低，但是這種方法的時(shí)間復(fù)雜度往往是指數(shù)級(jí)的，倘若不加優(yōu)化，其時(shí)間效率簡(jiǎn)直無法忍受；而廣度優(yōu)先搜索雖然時(shí)間復(fù)雜度比前者低一些，但其龐大的空間需求量又往往讓人望而卻步。     所以，對(duì)程序進(jìn)行優(yōu)化，就成為搜索算法編程中最關(guān)鍵的一環(huán)。     本文所要討論的便是搜索算法中優(yōu)化程序的一種基本方法棗“剪枝”。什么是剪枝     相信剛開始接觸搜索算法的人，都做過類似迷宮這樣的題目吧。我們?cè)凇白呙詫m”的時(shí)候，一般回

3、溯法思路是這樣的：     1、這個(gè)方向有路可走，我沒走過     2、往這個(gè)方向前進(jìn)     3、是死胡同，往回走，回到上一個(gè)路口     4、重復(fù)第一步，直到找著出口     這樣的思路很好理解，編程起來也比較容易。但是當(dāng)迷宮的規(guī)模很大時(shí)，回溯法的缺點(diǎn)便暴露無遺：搜索耗時(shí)極巨，無法忍受。     我們可不可以在向某個(gè)方向前進(jìn)時(shí)，先一步判斷出這樣走會(huì)不會(huì)走

4、到死胡同里呢？這樣一來，搜索的時(shí)間不就可以減少了嗎？     答案是：可以的。      剪枝的概念，其實(shí)就跟走迷宮避開死胡同差不多。若我們把搜索的過程看成是對(duì)一棵樹的遍歷，那么剪枝顧名思義，就是將樹中的一些“死胡同”，不能到達(dá)我們需要的解的枝條“剪”掉，以減少搜索的時(shí)間。搜索算法，絕大部分需要用到剪枝。然而，不是所有的枝條都可以剪掉，這就需要通過設(shè)計(jì)出合理的判斷方法，以決定某一分支的取舍。在設(shè)計(jì)判斷方法的時(shí)候，需要遵循一定的原則。剪枝的原則     1、正確性 &

5、#160;   正如上文所述，枝條不是愛剪就能剪的。如果隨便剪枝，把帶有最優(yōu)解的那一分支也剪掉了的話，剪枝也就失去了意義。所以，剪枝的前提是一定要保證不丟失正確的結(jié)果。     2、準(zhǔn)確性     在保證了正確性的基礎(chǔ)上，我們應(yīng)該根據(jù)具體問題具體分析，采用合適的判斷手段，使不包含最優(yōu)解的枝條盡可能多的被剪去，以達(dá)到程序“最優(yōu)化”的目的?？梢哉f，剪枝的準(zhǔn)確性，是衡量一個(gè)優(yōu)化算法好壞的標(biāo)準(zhǔn)。     3、高效性 設(shè)計(jì)優(yōu)化程序的根本目的，是要減少搜索的次數(shù)，使程

6、序運(yùn)行的時(shí)間減少。但為了使搜索次數(shù)盡可能的減少，我們又必須花工夫設(shè)計(jì)出一個(gè)準(zhǔn)確性較高的優(yōu)化算法，而當(dāng)算法的準(zhǔn)確性升高，其判斷的次數(shù)必定增多，從而又導(dǎo)致耗時(shí)的增多，這便引出了矛盾。因此，如何在優(yōu)化與效率之間尋找一個(gè)平衡點(diǎn)，使得程序的時(shí)間復(fù)雜度盡可能降低，同樣是非常重要的。倘若一個(gè)剪枝的判斷效果非常好，但是它卻需要耗費(fèi)大量的時(shí)間來判斷、比較，結(jié)果整個(gè)程序運(yùn)行起來也跟沒有優(yōu)化過的沒什么區(qū)別，這樣就太得不償失了。綜上所述，我們可以把剪枝優(yōu)化的主要原則歸結(jié)為六個(gè)字：正確、準(zhǔn)確、高效。剪枝算法按照其判斷思路可大致分成兩類：可行性剪枝及最優(yōu)性剪枝。下面分別結(jié)合例題對(duì)這兩種方法進(jìn)行闡述?？尚行约糁?#160;

7、    這個(gè)方向可不可以走？走下去會(huì)不會(huì)碰到死胡同？這就是對(duì)某一枝條進(jìn)行可行性剪枝的簡(jiǎn)要判斷過程。     我們現(xiàn)來看這樣一道題。     問題簡(jiǎn)述：一個(gè)規(guī)則矩形網(wǎng)絡(luò)狀的城市，城市中心坐標(biāo)為（0,0）。城市包含M個(gè)無法通行的路障(M<=50)，采用如下規(guī)則游歷城市：第一步走1格，第二步走2格，依此類推，第N步走n格(N<=20)，除了第一步有四個(gè)方向可走，其余各步必須在前一步基礎(chǔ)上左轉(zhuǎn)或右轉(zhuǎn)90度，最后回到出發(fā)點(diǎn)（0,0）。對(duì)于給定的N、M，編程求出所有可行的路徑。

8、0;    這道題為ACM競(jìng)賽中“黃金圖形”一題的簡(jiǎn)化，曾在GDKOI98中出為“數(shù)學(xué)家旅游”一題。     書中的解答采用了簡(jiǎn)單的回溯法，原因是該題的本身就已經(jīng)有很強(qiáng)的剪枝判斷了。那么我們先來分析一下用回溯法解題的思路：     用x，y兩個(gè)變量存儲(chǔ)當(dāng)前坐標(biāo)，每一步對(duì)x，y的值進(jìn)行修改，沒有遇到障礙就繼續(xù)走，走完n步看看有沒有回到（0,0），沒有的話回溯搜索，直到找完所有路徑。     接著，我們來看看這種算法的時(shí)間復(fù)雜度。 

9、0;   一共走n步，每步要搜索四個(gè)方向，假設(shè)在最壞的情況下，沒有任何障礙物，那么它的時(shí)間復(fù)雜度應(yīng)該為：O(4n)。很明顯，這樣的算法效率并不會(huì)很高，所以我們必須對(duì)程序進(jìn)行剪枝，在未走完n步之前就提早判斷出這樣的走法是否可行。當(dāng)走到第o步時(shí)，假設(shè)當(dāng)前坐標(biāo)為（xo，yo），那么離（0,0）的最遠(yuǎn)距離就應(yīng)該是Max(xo, yo)，而剩下的n-o步可以走的最遠(yuǎn)距離則是(o+1)+(o+2)+n，即。所以，若<Max(xo, yo)的話，就表示就算現(xiàn)在“回頭”也沒辦法到達(dá)出發(fā)點(diǎn)了，也就是說這條分支即便再搜索下去也找不出解來，這時(shí)我們已經(jīng)可以舍棄這一分支而回溯了。這樣剪枝似乎

10、已經(jīng)不錯(cuò)了，但是，它的效果只有當(dāng)數(shù)據(jù)較大時(shí)，才能體現(xiàn)得明顯。除了上述的優(yōu)化，還有沒有其他的方法呢？     我們可以這樣想，這個(gè)城市是規(guī)則矩形網(wǎng)絡(luò)狀的，東、南、西、北四個(gè)方向都是對(duì)稱的。打個(gè)比方說，與（1,0）這個(gè)點(diǎn)對(duì)稱的可以有（-1,0），（0,1），（0,-1）這三點(diǎn)。那可否設(shè)想，當(dāng)從一個(gè)方向出發(fā)，尋找到一個(gè)解之后，將這個(gè)解旋轉(zhuǎn)90o、180o、270o，不就得出其余三個(gè)解了么？這樣豈不是節(jié)省了3/4的搜索次數(shù)？     由這個(gè)設(shè)想出發(fā)，我們可以設(shè)計(jì)出下面的優(yōu)化：    

11、 忽略所有的障礙物，第一步固定走方向a（比如東面），在這個(gè)基礎(chǔ)上搜索路徑，每找到一條路徑都將其余三個(gè)“對(duì)稱路徑”一起判斷，看看有沒有經(jīng)過障礙物，若沒有則該路徑為解之一。     通過以上分析，我們已經(jīng)可以編出一個(gè)效率較高的搜索程序。請(qǐng)看下表：     “黃金圖形”的測(cè)試情況（單位：秒） N值 障礙物數(shù) 程序運(yùn)行時(shí)間 普通回溯 剪枝一 剪枝二 綜合優(yōu)化 8 2 <0.01 <0.01 <0.01 <0.01 12 4 0.06 0.05 0.06 <0.01 1500.360.220.1

12、10.051681.540.820.160.111865.662.850.650.3320010.055.172.581.26215038.5614.395.112.422450210.273.1142.8920.93     測(cè)試結(jié)果分析：     1、普通回溯法，在處理比較小的數(shù)據(jù)時(shí)，耗時(shí)還是比較低的，但當(dāng)規(guī)模擴(kuò)大到一定程度時(shí)，其時(shí)間復(fù)雜度呈指數(shù)級(jí)上升，因此競(jìng)賽時(shí)應(yīng)盡量避免使用單純的不加優(yōu)化的回溯法。     2、采用第一種剪枝方法，當(dāng)數(shù)據(jù)較小時(shí)與普通回溯法耗時(shí)相當(dāng)，數(shù)據(jù)

13、規(guī)模逐漸增大時(shí)，與回溯法的耗時(shí)差距便逐漸拉開，因?yàn)榧糁Φ卯?dāng)，搜索次數(shù)比不加優(yōu)化時(shí)至少減小了一半。     3、用對(duì)稱性來使時(shí)間復(fù)雜度減少一個(gè)指數(shù)級(jí)，從表中可以明顯看出優(yōu)化后的程序與完全不優(yōu)化的耗時(shí)簡(jiǎn)直不可同日而語，與前一剪枝方法比較，按照剪枝原則中準(zhǔn)確性原則來判斷，這種方法比前者要好。     4、綜合兩種剪枝方法，準(zhǔn)確性得到提高，耗時(shí)非常少。為了明顯比較出各種算法的優(yōu)劣，我將N值提高到24，結(jié)果綜合優(yōu)化的程序只需21秒便出解，耗時(shí)為普通回溯法十分之一。     5、這兩種剪

14、枝，以及綜合的剪枝方法，都遵循了正確性的原則。它們之間的差異主要是在準(zhǔn)確性與高效性兩點(diǎn)上?？梢哉f，最后一種優(yōu)化算法綜合了前兩種，既提高了準(zhǔn)確性，又保證了高效性，使得兩種剪枝優(yōu)勢(shì)互補(bǔ)，取得了非常優(yōu)秀的效果。競(jìng)賽中搜索程序常常使用不只一種的優(yōu)化方法，所要求達(dá)到的就是這種效果。最優(yōu)性剪枝     最優(yōu)性剪枝，又稱為上下界剪枝。我們可以回想一下，平時(shí)在做一些要求最優(yōu)解的問題時(shí)，搜索到一個(gè)解，是不是把這個(gè)解保存起來，若下次搜索到的解比這個(gè)解更優(yōu)，就又把更優(yōu)解保存起來？其實(shí)這個(gè)較優(yōu)解在算法中被稱為“下界”，與此類似還有“上界”。在搜索中，如果已判斷出這一分支的所有子

15、節(jié)點(diǎn)都低于下界，或者高于上界，我們就可以將它剪枝。     如何估算出上（下）界呢？我們引入一個(gè)概念棗“估價(jià)函數(shù)”。最優(yōu)性剪枝算法的核心，就在于設(shè)計(jì)估價(jià)函數(shù)上。估價(jià)函數(shù)在不同的題目中被賦予不同的意義，比如說當(dāng)前狀態(tài)與目標(biāo)狀態(tài)相差的步數(shù)，某一數(shù)列的長(zhǎng)度等等，都可作為估價(jià)函數(shù)的一部分。     我們?cè)賮砜匆坏李}目：     問題簡(jiǎn)述：在一個(gè)N*M的迷宮矩陣中，有X個(gè)不可逾越的障礙物，給定x0, y0, x1, y1, 求出由(x0, y0)到(x1, y1)之間的所有路徑。這一道

16、題看起來非常簡(jiǎn)單，也與上一題有不少相似之處。難道我們不能用簡(jiǎn)單的回溯法來解決它嗎？我們來分析一下時(shí)間復(fù)雜度。與上題類似，我們同樣假設(shè)在最壞情況下，迷宮中沒有任何障礙，即是一個(gè)坦蕩蕩的矩形，從(0,0)到(n,m)的話，每一步有四個(gè)方向可以走，時(shí)間復(fù)雜度將達(dá)到O(4n*4m)！假設(shè)n=m=20，那么搜索次數(shù)將達(dá)到242次！看來這“枝”是非“剪”不可了。     最初步的剪枝當(dāng)然就是將走過的方格置為“障礙”，因?yàn)槿糁貜?fù)通過同一格，最終結(jié)果必定不是最優(yōu)解。     其次，我們可以將每一次搜索出的路徑長(zhǎng)度與上界比較（初始下

17、界），不斷降低上界，一旦出現(xiàn)路徑長(zhǎng)超出上界而仍未到達(dá)目標(biāo)點(diǎn)，則放棄該搜索進(jìn)程。因?yàn)榫退憷^續(xù)搜索下去，這一條路徑也必然比其他路徑長(zhǎng)，不是最優(yōu)解。要完成規(guī)模更大的迷宮，僅僅這樣剪枝是不夠的。我們還必須采取其他的方法，比如先用動(dòng)態(tài)規(guī)劃求出一個(gè)準(zhǔn)確的上界，再依據(jù)此上界進(jìn)行搜索等。     當(dāng)然，對(duì)于迷宮這一類題目，搜索算法并不是最好的。我們完全可以用標(biāo)號(hào)法填滿一個(gè)二維矩陣，再用簡(jiǎn)單的回溯法進(jìn)行輸出。在這里引用這樣的一道題，目的是想讓讀者更好的理解最優(yōu)化剪枝的思路及其應(yīng)用，起到拋磚引玉的作用?！懊詫m問題”的測(cè)試情況（單位：秒）N值M值障礙物數(shù)程序運(yùn)行時(shí)間普通回溯普

18、通定界動(dòng)態(tài)規(guī)劃+定界441<0.01<0.01<0.016624.12<0.01<0.01880Very long4.070.1110100Very longVery long1.70121210Very longVery long5.77141460Very long8.950.06     結(jié)合本題，我們可以得出最優(yōu)化剪枝算法所應(yīng)該注意的一些問題：     1、與可行性剪枝一樣，最優(yōu)性剪枝在保證正確性的同時(shí)，同樣需要注意提高準(zhǔn)確性和高效性，估價(jià)函數(shù)的計(jì)算極為頻繁，必須盡量提高其運(yùn)算

19、效率，不要“揀了芝麻，掉了西瓜”，尋找準(zhǔn)確與高效的平衡點(diǎn)，確實(shí)重要。     2、在使用最優(yōu)化剪枝時(shí)，一個(gè)好的估價(jià)函數(shù)往往起到“事半功倍”的效果。在搜索之前，我們可以采用一些高效率的算法，如貪心法、動(dòng)態(tài)規(guī)劃、標(biāo)號(hào)法等等，求出一個(gè)較優(yōu)解，作為上（下）界，將有解的范圍縮小，以盡可能的剪去多余的枝條。如上表中最后一種算法，采用動(dòng)態(tài)規(guī)劃求出上界，再進(jìn)行搜索，效率提高了許多。     此外，不但深度優(yōu)先搜索可以運(yùn)用最優(yōu)性剪枝，在廣度優(yōu)先搜索中，同樣可以采用這種剪枝方法。比較典型的算法有：分支定界法、A*算法，博弈樹等等。不過

20、，這些方法一般空間復(fù)雜度都比深度優(yōu)先搜索要大得多，如何取舍就要依據(jù)不同的題目作出相應(yīng)的判斷了?？?結(jié)     在搜索算法中，幾乎都需要采用程序優(yōu)化，以減少時(shí)間復(fù)雜度。而本文所論述的“剪枝”算法，就是最常見的優(yōu)化方法之一。編優(yōu)化程序的過程中，不論運(yùn)用的是可行性剪枝還是最優(yōu)性剪枝，都離不開剪枝的三個(gè)原則棗正確、準(zhǔn)確、高效，可以說，它們就是剪枝算法的“生命”。     然而，盡管可以采用眾多優(yōu)化算法使得程序的效率有所提高，搜索算法本身的時(shí)間復(fù)雜度不能從本質(zhì)上減少是不可改變的事實(shí)，我們?cè)诳紤]對(duì)一道題采用搜索算法之前，不妨先

21、仔細(xì)想想，有沒有其他更好的算法。畢竟，優(yōu)化程序也是一項(xiàng)“吃力不討好”的工作，與其耗費(fèi)大量的時(shí)間來優(yōu)化搜索程序，倒不如多想，多寫，盡量以非搜索算法解決問題。總之，我們?cè)诟?jìng)賽中應(yīng)當(dāng)多動(dòng)動(dòng)腦筋，從不同角度來思考問題，采取合適的算法解決問題?！緟⒖紩俊?#160;    1、齊鑫論文搜索方法中的剪枝優(yōu)化     2、吳文虎主編ACM國際大學(xué)生程序設(shè)計(jì)競(jìng)賽試題與解析（一）     3、吳文虎、王建德編著實(shí)用算法的分析與程序設(shè)計(jì)【程 序】一、用“綜合優(yōu)化”解決黃金圖形源程序： backtrack

22、ing method Const     input = 'golygon.dat'     output= 'golygon.out'     path : Array 1.4, 1.2 of integer =                (1, 0), (0, -1), (-1, 0), (0, 1

23、);     head : Array 1.4 of char =               ('e', 's', 'w', 'n');     clogs = 50; m <= clogs      ways = 24; n <= ways Var 

24、    fp : text;     n, 最長(zhǎng)步數(shù)      m, 障礙物數(shù)      o 路徑指針           : byte;     clog : Array 1.clogs of   儲(chǔ)存障礙物坐標(biāo)      Record x, y : int

25、eger End;     way : Array 0.ways of byte; 儲(chǔ)存路徑      results : integer; 路徑數(shù) Procedure _init; 初始化 Var i : byte;Begin     Assign(fp, input); Reset(fp);     Readln(fp, n); Readln(fp, m);     for i := 1 to

26、 m do     Readln(fp,clogi.x, clogi.y);     Close(fp);     Assign(fp, output); Rewrite(fp)End;Procedure _out; 輸出路徑 Var i, j, t : byte; x, y : integer;     b : boolean;Begin     for j := 1 to 4 do  

27、;    Begin          x := 0; y := 0; b := TRUE;          for i := 1 to o do           Begin          

28、     x := x+pathwayi1*i;               y := y+pathwayi2*i;               for t := 1 to m do        &

29、#160;           if(x=clogt.x) and(y-pathwayi2*i<clogt.y)                         and(y >= clogt.y) or (y-pathwayi2*i > cl

30、ogt.y)                         and(y <= clogt.y) or (y = clogt.y)                   

31、60;      and(x-pathwayi1*i < clogt.x)                         and(x >= clogt.x) or (x-pathwayi1*i > clogt.x)      &#

32、160;                  and(x <= clogt.x)                             

33、; 如果通過障礙物                     then Begin b := FALSE; Break End;               if not b then Break      &#

34、160;   End;          if b then           Begin               Inc(results);         &#

35、160;     for i := 1 to o do Write(fp, headwayi);               Writeln(fp)          End;          for i := 1 to o do way

36、i := wayi mod 4 + 1 旋轉(zhuǎn)路徑      EndEnd;Function _sum(step : integer) : integer;Var i, r : integer;Begin     r := 0;     for i := step+1 to n do Inc(r, i);     _sum := rEnd;Function _is_able_to_pass (x, y, i, step : integer

37、) : boolean;Var t : integer;Begin     _is_able_to_pass := TRUE;     if (abs(x) > _sum(step) or          (abs(y) > _sum(step) or      不能“回頭”了？         

38、;  (i = wayo)           重復(fù)走同一個(gè)方向了？           or (abs(i-wayo) = 2) 折返了？      then _is_able_to_pass := FALSEEnd;Procedure _main(step, x, y : integer); step 第幾步 x, y 當(dāng)前坐標(biāo) Var i : byte;Begi

39、n      if (x = 0) and (y = 0) and (step = n+1)then      Begin          _out; 若到達(dá)（0,0）則輸出，回溯 Exit      End;     if step > n then Exit; 如果超過步數(shù)沒有回到起點(diǎn)就回溯    

40、0; for i := 1 to 4 do 嘗試每個(gè)方向           if _is_able_to_pass 如果通行 (x+pathi1*step, y+pathi2*step, i, step) then           Begin               I

41、nc(o); wayo := i; 存下路徑                _main(step+1, 走下一步                     x+pathi1*step, y+pathi2*step); 改變坐標(biāo)    

42、0;           Dec(o) 恢復(fù)原來的路徑           EndEnd;Procedure _exit;Begin     Writeln(fp, 'Found ', results, ' golygon(s).');     Close(fp)End;Begin &#

43、160;   _init;     o := 1; way1 := 1;     _main(2, 1, 0);     _exitEnd.二、用動(dòng)態(tài)規(guī)劃求上界再搜索的迷宮問題源程序：(為了便于測(cè)試，沒有輸出路徑)Const     input = 'trip.dat'     output= 'trip.out'  

44、0;  path : Array 1.4, 1.2 of shortint =          (-1, 0), (1, 0), (0, -1), (0, 1);     maxn = 30;     maxm = 30;Var     fp : text;     n, m, x0, y0, x1, y1, all, o, resul

45、ts, xx : longint;          all 路徑總數(shù)；results 上界      r : Array 1.maxn, 1.maxm of shortint;          迷宮，0-可行，-1 障礙      way : Array 1.1000 of byte; 儲(chǔ)存路徑    &

46、#160; l : Array 1.maxn, 1.maxm of integer; 動(dòng)態(tài)規(guī)劃的數(shù)組 Procedure _init;Var a, b, x : byte;Begin     Assign(fp, input); Reset(fp);     Readln(fp, n, m, x);     for x := x downto 1 do      Begin     &#

47、160;    Readln(fp, a, b);          ra,b := -1     End;     Readln(fp, x0, y0, x1, y1);     Close(fp);     Assign(fp, output); Rewrite(fp)End;Procedure _solve; 動(dòng)

48、態(tài)規(guī)劃 Var i, j, k : integer; b : boolean;Begin     lx0,y0 := 1;     Repeat          b:= TRUE;          for i := 1 to n do         &#

49、160;      for j := 1 to m do                     for k := 1 to 4 do                   

50、;      if (li,j > 0) then                              if (i+pathk1 > 0)         

51、60;                     and (i+pathk1 <= n)                         

52、0;    and (j+pathk2 > 0)                               and (j+pathk2 <= m) then 沒越界         &#

53、160;                          if (ri+pathk1,j+pathk2 <> -1) then 不是障礙                 

54、60;                       if (li,j+1 < li+pathk1,j+pathk2) or                     

55、                        (li+pathk1,j+pathk2 = 0) then                       

56、;                  Begin                                

57、;             li+pathk1,j+pathk2 := li,j + 1;                                

58、60;                 填數(shù)組，lI,j表示該格的“估價(jià)值”