ACM專題——搜索算法1

1、ACM專題講座搜索算法 12搜索算法1. 搜索問題2. 搜索方法分類3. 回溯方法4. 一般圖搜索算法 5. 啟發(fā)式搜索算法31.搜索問題人類的思維過程，可以看作一個搜索過程。我們遇到的很多智力游戲問題，如傳教士和野人問題。 有3個傳教士和3個野人來到河邊準備渡河，河岸有一條船，每次最多可乘坐2個人。問傳教士為安全起見，應如何規(guī)劃擺渡方案，使得在任何時刻，在河的兩岸以及船上傳教士人數(shù)不能少于野人的人數(shù)？對這個問題，在每一次渡河后，都會有幾種渡河方案供選擇，究竟哪種方案最有利？ 這就是搜索問題。41.搜索問題對這類問題，一般我們都轉(zhuǎn)換為狀態(tài)空間的搜索問題。如傳教士和野人問題，可用在河左岸的傳教士

2、人數(shù)、野人人數(shù)和船的情況來表示。即，初始時狀態(tài)為（3，3，1），結(jié)束狀態(tài)為（0，0，0），而中間狀態(tài)可表示為（2，2，0）、（3，2，1）等等。 初始狀態(tài) 結(jié)束狀態(tài) L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 151.搜索問題由此，可以看出這類問題的解，就是一個合法狀態(tài)的序列，其中序列中第一個狀態(tài)是問題的初始狀態(tài)，而最后一個狀態(tài)則是問題的結(jié)束狀態(tài)。如圖所示即搜索問題的示意圖：SgS0解路徑解路徑搜索空間搜索空間全狀態(tài)空間全狀態(tài)空間62.搜索方法分類不可撤回方法不可撤回方法試探性方法試探性方法回溯方法回溯方法圖搜索方法圖搜索方法73. 回溯方法回溯方法，屬

3、于盲目搜索的一種，它是這樣一種策略：首先將規(guī)則給出一個固定的排序，在搜索時，對當前狀態(tài)依次檢測每一條規(guī)則，在當前狀態(tài)未使用過的規(guī)則中找到第一條可應用規(guī)則，應用于當前狀態(tài)，得到的新狀態(tài)重新設(shè)置為當前狀態(tài)，并重復以上搜索。如果當前狀態(tài)無規(guī)則可用，或者所有規(guī)則已經(jīng)被試探過仍未找到問題的解，則將當前狀態(tài)的前一個狀態(tài)（即直接生成該狀態(tài)的狀態(tài)）設(shè)置為當前狀態(tài)。重復以上搜索，直到找到問題的解，或已試探過所有可能仍找不到問題的解為止。83. 回溯方法 對于用回溯法求解的問題，首先要將問題進行適當?shù)霓D(zhuǎn)化，得出狀態(tài)空間樹。 這棵樹的每條完整路徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹，枚舉每種可能的解的情況；

4、從而得出結(jié)果。但是，回溯法中通過構(gòu)造約束函數(shù)，可以大大 提升程序效率，因為在深度優(yōu)先搜索的過程中，不斷的將每個解（并不一定是完整的，事實上這也就是構(gòu)造約束函數(shù)的意義所在）與約束函數(shù)進行對照從而刪除一些 不可能的解，這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時間。93. 回溯方法回溯法中，首先需要明確下面三個概念： （一）約束函數(shù)：約束函數(shù)是根據(jù)題意定出的。通過描述合法解的一般特征用于去除不合法的解，從而避免繼續(xù)搜索出這個不合法解的剩余部分。因此，約束函數(shù)是對于任何狀態(tài)空間樹上的節(jié)點都有效、等價的。 （二）狀態(tài)空間樹：剛剛已經(jīng)提到，狀態(tài)空間樹是一個對所有解的圖形描述。樹上的每個子節(jié)點的解都只有

5、一個部分與父節(jié)點不同。 （三）擴展節(jié)點、活結(jié)點、死結(jié)點：所謂擴展節(jié)點，就是當前正在求出它的子節(jié)點的節(jié)點，在DFS中，只允許有一個擴展節(jié)點?；罱Y(jié)點就是通過與約束函數(shù)的對照，節(jié)點本身和其父節(jié)點均滿足約束函數(shù)要求的節(jié)點；死結(jié)點反之。由此很容易知道死結(jié)點是不必求出其子節(jié)點的（沒有意義）。103. 回溯方法深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（FIFO） 在分支界限法中，一般用的是FIFO或最小耗費搜索；其思想是一次性將一個節(jié)點的所有子節(jié)點求出并將其放入一個待求子節(jié)點的隊列。通過遍歷這個隊列（隊列在 遍歷過程中不斷增長）完成搜索。而DFS的作法則是將每一條合法路徑求出后再轉(zhuǎn)而向上求第二條合法路徑。而在回

6、溯法中，一般都用DFS。為什么呢？這是因 為可以通過約束函數(shù)殺死一些節(jié)點從而節(jié)省時間，由于DFS是將路徑逐一求出的，通過在求路徑的過程中殺死節(jié)點即可省去求所有子節(jié)點所花費的時間。FIFO 理論上也是可以做到這樣的，但是通過對比不難發(fā)現(xiàn)，DFS在以這種方法解決問題時思路要清晰非常多。 因此，回溯法可以被認為是一個有過剪枝的DFS過程。 113. 回溯方法利用回溯法解題的具體步驟 首先，要通過讀題完成下面三個步驟： (1)描述解的形式，定義一個解空間，它包含問題的所有解。 (2)構(gòu)造狀態(tài)空間樹。 (3)構(gòu)造約束函數(shù)（用于殺死節(jié)點）。 123. 回溯方法然后就要通過DFS思想完成回溯，完整過程如下：

7、(1)設(shè)置初始化的方案（給變量賦初值，讀入已知數(shù)據(jù)等）。 (2)變換方式去試探，若全部試完則轉(zhuǎn)(7)。 (3)判斷此法是否成功（通過約束函數(shù)），不成功則轉(zhuǎn)(2)。 (4)試探成功則前進一步再試探。 (5)正確方案還未找到則轉(zhuǎn)(2)。 (6)已找到一種方案則記錄并打印。 (7)退回一步（回溯），若未退到頭則轉(zhuǎn)(2)。 (8)已退到頭則結(jié)束或打印無解。13 修道士和野人問題編程實現(xiàn) 過河問題的求解：三個修道士和三個野人過河，船一次最多只能載兩個人，在任何時候修道士的人數(shù)不能少于野人人數(shù)，否則野人會吃掉修道士。找出六個人順利過河的所有方案。 14整體思想 采用四元組（修道士人數(shù)03，會劃船野人數(shù)02

8、，不會劃船野人數(shù)0/1，船所在岸0/1）描述結(jié)點狀態(tài)，開始狀態(tài)為（3，2，1，0），目標狀態(tài)為（0，0，0，1）。采用帶回溯的深度優(yōu)先搜索策略，共定義了7種合法操作2,0,0,1,0,0,1,1,0,0,1,0,0,2,0,0,1,1,1,0,1代表上船的人數(shù)，根據(jù)船所在位置決定在狀態(tài)上是加或者減操作。擴展結(jié)點時按順序應用操作，直到回溯到初始狀態(tài)且所有操作用完，程序結(jié)束。 15類設(shè)計 state類：描述狀態(tài)結(jié)點，包括描述狀態(tài)的相關(guān)成員變量和操作變量的成員函數(shù) river類：描述和解決過河問題 16【算法和數(shù)據(jù)結(jié)構(gòu)】 1算法 采用帶回溯的深度優(yōu)先策略。 在每個合法結(jié)點上應用所有7種操作，生成所有

9、結(jié)點，然后判斷結(jié)點的合法與否，確定是否回溯。每找到一種方法只要沒有生成所有結(jié)點則回溯繼續(xù)搜索。直到回溯到初始結(jié)點并且初始結(jié)點的所有操作已經(jīng)應用完畢，則整個搜索過程結(jié)束。 2.數(shù)據(jù)結(jié)構(gòu) 采用鏈表結(jié)構(gòu)，結(jié)點是生成的狀態(tài)，當前結(jié)點在鏈表頭。結(jié)點中包含狀態(tài)信息和程序需要的相關(guān)控制信息。新擴展生成的結(jié)點放在鏈表頭，回溯時刪除頭結(jié)點并移動頭指針。當找到一種過河方案時，當前鏈表中的所有結(jié)點就是按順序生成的狀態(tài)結(jié)點，只要遍歷鏈表輸出狀態(tài)就可以得到該種方法經(jīng)過的狀態(tài)和所用的操作。17N皇后問題 問題描述： 在一個N*N的棋盤上放置N個皇后，且使得每兩個之間不能互相攻擊，也就是使得每兩個不在同一行，同一列和同一斜

10、角線上。183. 回溯方法n例：皇后問題QQQQ193. 回溯方法( )( )203. 回溯方法( )( )(1,1)Q213. 回溯方法( )( )(1,1)(1,1) (2,3)QQ223. 回溯方法( )( )(1,1)(1,1) (2,3)Q233. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)QQ243. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)QQQ253. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)QQ263. 回溯方

11、法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q273. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)283. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)Q293. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)QQ303. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)(1,2) (2,4) (3,1)QQQ313. 回溯方法( )( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)(1,2) (2,4) (3,1)(1,2) (2,4) (3,