搜索剪枝常見方法與技巧

《搜索剪枝常見方法與技巧》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、搜索剪枝常見方法與技巧關(guān)鍵字搜索方法,剪枝摘要搜索是計(jì)算機(jī)解題中常用的方法，它實(shí)質(zhì)上是枚舉法的應(yīng)用。由于它相當(dāng)于枚舉法，所以其效率是相當(dāng)?shù)氐摹Ｒ虼?，為了提高搜索的效率，人們想出了很多剪枝的方法，如分枝定界，啟發(fā)式搜索等等。在競(jìng)賽中，我們不僅要熟練掌握這些方法，而且要因地制宜地運(yùn)用一些技巧，以提高搜索的效率。正文搜索的效率是很低的，即使剪枝再好，也無法彌補(bǔ)其在時(shí)間復(fù)雜度上的缺陷。因此，在解題中，除非其他任何方法都行不通，才可采用搜索。既然采用了搜索，剪枝就顯得十分的必要，即使就簡(jiǎn)簡(jiǎn)單單的設(shè)一個(gè)檻值，或多加一兩條判

2、斷，就可對(duì)搜索的效率產(chǎn)生驚人的影響。例如Ｎ后問題，假如放完皇后再判斷，則僅僅只算到７，就開始有停頓，到了８就已經(jīng)超過了２０秒，而如果邊放邊判斷，就算到了１０，也沒有停頓的感覺。所以，用搜索就一定要剪枝。剪枝至少有兩方面，一是從方法上剪枝，如采用分枝定界，啟發(fā)式搜索等，適用范圍比較廣；二是使用一些小技巧，這類方法適用性雖不如第一類，有時(shí)甚至只能適用一道題，但也十分有效，并且?guī)缀趺康李}都存在一些這樣那樣的剪枝技巧，只是每題有所不同而已。問題一：(最短編號(hào)序列)表A和表B各含k(k<=20)個(gè)元素，元素編號(hào)從1到k。

3、兩個(gè)表中的每個(gè)元素都是由0和1組成的字符串。（不是空格）字符串的長度<=20。例如下表的A和B兩個(gè)表，每個(gè)表都含3個(gè)元素（k=3）。16元素編號(hào)字符串11210111310表A表B元素編號(hào)字符串111121030對(duì)于表A和表B，存在一個(gè)元素編號(hào)的序列2113，分別用表A中的字符串和表B中的字符串去置換相應(yīng)的元素編號(hào)，可得相同的字符串序列101111110，見下表。元素編號(hào)序列2113用表A的字符串替換101111110用表B的字符串替換101111110對(duì)表A和表B，具有上述性質(zhì)的元素編號(hào)序列稱之為S(AB)。

4、對(duì)于上例S(AB)=2113。編寫程序：從文件中讀入表A和表B的各個(gè)元素，尋找一個(gè)長度最短的具有上述性質(zhì)的元素編號(hào)序列S(AB)。（若找不到長度<=100的編號(hào)序列，則輸出“NoAnswer”。對(duì)于這道題，因?yàn)楸恚梁捅恚虏淮_定，所以不可能找到一種數(shù)學(xué)的方法。因?yàn)樗蟮氖亲顑?yōu)解，而深度優(yōu)先搜索很容易進(jìn)入一條死胡同而浪費(fèi)時(shí)間，所以必須采用廣度優(yōu)先搜索的方法。但是，廣度優(yōu)先搜索也有其缺陷。當(dāng)表Ａ和表Ｂ中的元素過多是，擴(kuò)展的結(jié)點(diǎn)也是相當(dāng)多的，搜索所耗費(fèi)的時(shí)間也無法達(dá)到測(cè)試的要求。為了解決這個(gè)問題，就必須對(duì)搜索的算法加以

5、改進(jìn)。分枝限界似乎不行，因?yàn)闊o法確定代價(jià)。而且，由于目標(biāo)不確定，也無法設(shè)定估價(jià)函數(shù)。但是，因?yàn)榇祟}的規(guī)則既可以正向使用，又可以逆向使用，于是便可以采用雙向搜索。在大方法確定后，算法的框架就已經(jīng)基本形成，但即使如此，算法也還有可改進(jìn)的地方。1.存儲(chǔ)當(dāng)前的Ａ串和Ｂ串是很費(fèi)空間的，但因?yàn)椋链停麓拇蟛糠窒嗤?，故只需記錄不同部分，并作個(gè)標(biāo)記。再換成動(dòng)態(tài)存儲(chǔ)。2.為了保證兩個(gè)方向擴(kuò)展結(jié)點(diǎn)的速度相對(duì)平衡，可以采取每次擴(kuò)展結(jié)點(diǎn)數(shù)較少的方向，而不是兩方向輪流擴(kuò)展。如此一來，搜索的效率就比單純的廣度優(yōu)先搜索有了明顯的提高。（附

6、程序sab.pas）有時(shí)，搜索也會(huì)有不同的搜索方法（如多處理機(jī)調(diào)度問題），也會(huì)產(chǎn)生不同的效率。問題二：（任務(wù)安排）16Ｎ個(gè)城市，若干城市間有道路相連，一輛汽車在城市間運(yùn)送貨物，總是從城市１出發(fā)，又回到城市１。該車每次需完成若干個(gè)任務(wù)，每個(gè)任務(wù)都是要求該車將貨物從一個(gè)城市運(yùn)送至另一個(gè)。例如若要完成任務(wù)２－>6，則該車一次旅程中必含有一條子路徑。先到２，再到６。如下圖所示，如果要求的任務(wù)是２－>３，２－>４，３－>１，２－>５，６－>４，則一條完成全部任務(wù)的路徑是１－>２－>３－>１－>２－>５－>６－>４－>１。

7、　　　　　　4１　　2　　　　　　6　　　　　　　5　　3　　　　　7編程由文件讀入道路分布的領(lǐng)接矩陣，然后對(duì)要求完成的若干任務(wù)，尋找一條旅行路線，使得在完成任務(wù)最多的前提下，經(jīng)過的城市總次數(shù)最少。如上例中經(jīng)過城市總次數(shù)為８，城市１和２各經(jīng)過２次均以２次計(jì)（起點(diǎn)不計(jì)），Ｎ<60。這道題，因?yàn)楹茈y找到數(shù)學(xué)規(guī)律，便只有采用搜索的方法。首先，第一感覺便是：從城市i出發(fā)，便搜索所有相鄰的城市，再根據(jù)當(dāng)前所處的城市，確定任務(wù)的完成情況，從中找到最優(yōu)解。這種搜索的效率是極低的，其最大原因就在于：目標(biāo)不明確。根據(jù)題意，我們只

8、需到達(dá)需上貨和下貨的城市，其它的城市僅作為中間過程，而不應(yīng)作為目標(biāo)。因此，首先必須確定可能和不可能完成的任務(wù)，然后求出任意兩城市間的最短路徑。在搜索時(shí)，就只需考慮有貨要上的城市，或者是要運(yùn)到該城市的貨全在車上，其它不須考慮。同時(shí)，還可以設(shè)定兩個(gè)簡(jiǎn)單的檻值。如果當(dāng)前費(fèi)用+還需達(dá)的城市>=當(dāng)前最優(yōu)解，或當(dāng)前費(fèi)用+返回城市1的費(fèi)用>=當(dāng)前最優(yōu)解，則不需繼續(xù)往下搜索。這種方法與第一感的方法有天