1、第十三課 搜索算法12.0 搜索樹12.1 搜索算法的基本原理12.2 廣度優先搜索12.3 深度優先搜索12.4 練習12.0 搜索樹引例：在一個4*4的棋盤上的左下角有一個馬，按照國際象棋的規則，將這個馬跳到右*上角。分析：首先建立棋盤的坐標，我們以左下角為(1,1)，以右上角、為(4,4)。按照馬的移動規則，假定當前馬的位置坐標為(x,y)，則移動方法有：（1）x=x+1; y=y+2（2）x=x+1; y=y-2;（3）x=x+2; y=y+1;（4）x=x+2; y=y-1;（5）x=x-1; y=y+2;（6）x=x-1; y=y-2;（7）x=x-2; y=y+1;（8）x=x-

2、2; y=y-1113223122113314424114244112332232343233234123243213244可以建立搜索樹如下：圖中表示：由(1,1)可以跳到(2,3)和(3,2)兩個點(其它移動規則由于邊界限制無法到達)；(2,3)又可以跳到(1,1)、(4,4)、(4,2)、(3,1)四個點，(3,2)可以跳達(1,1)、(1,3)、(2,4)、(4,4)四個點，。搜索樹：按照數據元素的產生式規則建立起來的數據元素邏輯關系。特點：（1）數據之間的邏輯關系為一對多。 （2）每個結點數據的下一級子結點是由該結點的產生式規則生成。 （3）目標結點（答案數據）一定在搜索樹中能夠出現

3、。 （4）對于數據規模較大的問題，搜索樹的結點將是海量的。 （5）搜索樹可能是無窮無盡的（因為很多結點回重復出現）。12.1 搜索算法的基本原理：從搜索樹中可以看出，一個問題從起始狀態，通過窮舉的方式建立起搜索樹后，目標狀態一定能在搜索樹中出現。因此，只要建立起搜索樹，就可以在其中搜索到目標狀態（數據、路徑、位置等）。搜索算法要解決的問題：產生式規則：由當前狀態按照問題的需求和限制，生成新的狀態的方法集合。搜索樹的生成和存儲：一般采用一邊生成，一邊搜索；存儲方法有：集合、棧。搜索的方法：按行搜索：即從上到下，逐層搜索雙向按行搜索：一邊從上往下（起始狀態到中間狀態），一邊從下往上逐層搜索（從目標

4、狀態到中間狀態），找到相同的中間狀態即可。回朔法搜索：優先向更深層結點查找，走不通則換一條路，無法換則退回到上一層。搜索狀態的減少：在生成搜索樹時，對于已搜過的中間狀態的再次出現，是否需要再次加入到樹中重新搜索。12.2 廣度優先搜索（bfs）又稱寬度優先搜索，是一種從搜索樹的根結點開始，沿著樹的寬度遍歷樹的結點。如果所有節點均被訪問，則算法中止。一般用于求從起始狀態到目標狀態所需的最少步驟數。算法過程：1、首先將根結點放入隊列中。 2、從隊首取出一個結點，按照產生式規則逐個生成新的結點數據，對新數據： 如果如果是目標結點，則結束算法并返回結果。 如果不是目標結點，則檢查它是否已在搜索樹中出現

5、過，未出現就將它作為尚未檢查過的子結點加入到隊列的隊尾（特殊情況下，也有已出現過的結點重新入隊的）。 3、重復步驟2。4、若隊列為空，表示整張圖都檢查過了，即目標無法達到，結束算法并返回“找不到目標”的信息。 算法細化：用哈希數組判斷新生成的結點數據是否已出現過。隊列經常要多開一行，記錄新結點的父親（即該結點由上一層的哪個結點擴展而來），用于最后輸出過程。如數據規模過大，需要使用循環隊列（后果是無法記錄父親）。算法框架：function creat(i)begin case i of 1:creat:=按照第一產生式規則生成新狀態數據； 2:creat:=按照第二產生式規則生成新狀態數據； .

6、 . . end;end;/procedure bfs;begin join(起始狀態); while not(隊空) do begin 當前處理狀態:=deq; for i:=第一產生式規則 to 最大產生式規則 do begin 新狀態:=creat(i); if 新狀態=目標狀態 then begin print; exit; end else if not(haxi新狀態) then begin join(新狀態); haxi新狀態:=true; end; end; end;end;空間復雜度：線性隊列：O(最大可能狀態數)循環隊列：O(最大可能狀態數/2)時間復雜度：最差情形下，BF

7、S必須尋找所有到可能結點的所有路徑。O(最大可能狀態數)完全性：廣度優先搜索算法具有完全性。只要目標存在，則BFS一定會找到。但是，若目標不存在，且問題規模為無限大，則BFS將不收斂（不會結束）。適用范圍：廣度優先搜索是找到第一個解的算法，即距離根結點的邊數最少的解。如果所有邊的權值都相等（即所有產生新狀態的代價相同），則這個解也是最優解。例一：將一個馬從M*N的棋盤的左下角跳到右上角，需要的最少步數是多少？分析：1、用一個1.2,1.m*n的數組作為工作隊列，用于存儲搜索樹。 2、使用m*n的二維哈希數組判重。 3、生成搜索樹的同時，記錄父節點的序號和新結點的層數。 4、最后從目標結點向起始

8、結點回朔，用一個棧存儲回朔的中間狀態。例二：在一個2n+1的一維棋盤上，有n個黑色棋子和n個白色棋子，初始狀態如圖：規定棋子移動規則如下：如果某棋子的旁邊正好為空，這枚棋子可以移動到空位置上。如果某棋子的一側有棋子，二那枚棋子的另一側為空位置，這枚棋子可以跳過那枚棋子到空位置上。問：最少經過多少步，可以將棋盤狀態變成分析：用2n+1位三進制數表示狀態，如初始狀態為：222201111，目標狀態為111102222。轉化為十進制進行存儲，另記錄空格位置。產生式規則：將棋子移動轉化為空格的移動。空格向左移動空格向右移動空格向左跳動空格向右跳動用一個1.32n+1的哈希數組判重。例三：八數碼問題。在

9、一個的九宮中有這個數及一個空格隨機的擺放在其中的格子里，如圖所示。現在要求實現這個問題：將該九宮格調整為如圖2所示的形式。調整的規則是：每次只能將與空格（上、下、或左、右）相鄰的一個數字平移到空格中。試編程實現這一問題的求解。 1238476512345678圖一圖二分析：1、字符串表達狀態，另開一變量w記錄空格位置。 2、空格移動規則：（1）向下移動：w=w+3。（2）向上移動：w=w-3。（3）向左移動：w=w-1。（4）向右移動：w=w+1。 3、用窮舉法判重。（將來可以用排序二叉樹判重）12.3 深度優先搜索（dfs）深度優先搜索是從根結點出發，沿著樹的深度遍歷樹的結點。如果當前新產生

10、的結點還有以此為根的下一層結點，則沿此路繼續下去，直到無法再深入訪問時，回朔到上一層的結點，選另一條路繼續深入訪問。反復此過程，直到所有結點都被訪問到為止。算法過程：首先將根結點放入棧中。取出棧頂結點，按照產生式規則生成新的結點數據，每產生一個：檢查是否是目標結點，如果是且比保存的數據更優，刷新所保存的數據。檢查該結點是否已搜過，如果是且比已保存的數據更優，則刷新所保存的數據，然后該結點進棧；如沒有搜過，則保存數據并進棧。轉第二步。如果棧空，則算法結束。細化說明：一般用回朔法，利用遞歸使用系統棧。哈希數組不僅用于判斷新結點是否出現過，還用于保存到達該結點時的中間數據。算法框架：procedur

11、e dfs(結點數據);var i:integer;begin for i:=產生式規則一 to 最大產生式規則 do begin 新結點數據:=creat(i); if (新結點數據沒有搜到過)or(新結點數據雖已搜過但本次搜索結果更優) then begin更新新結點搜索結果;dfs(新結點數據); end;end;procedure dfs(結點數據);var i:longint;beginfor i:=1 to 最大產生式規則 dobegin新結點:=creat(i);if 新結點是目標結點 thenbegin傳回新結點;t:=true;exit;end;if 新結點更優 thenbe

12、gin更新新結點數據;dfs(新結點);if t then exit;end;end;end;空間復雜度：O(最大狀態數) （主要用于存儲各結點搜索結果）時間復雜度：O(最大產生式規則數最大狀態數)深度優先搜索的理論依據是建立在窮舉基礎上的，所以時間是幾何級數級的，其優化剪枝是非常必要的，因此，深搜的主要算法設計是在于如何剪枝，如何既高效地拋棄不必要的子樹，又不至于將最優解剪掉，將是深搜的最大難點。適用范圍：在缺乏有效的數學方法、遞推算法，不符合動態規劃要求，也沒有專用算法可以應對，一般考慮使用深搜；得分情況將取決于優化剪枝的技巧（30-100分）。例一：有A、B、C、D、E 5本書，要分給張

13、、王、劉、趙、錢5位同學，每人只能選1本。每個人都將自己喜愛的書填寫在下表中。請你設計一個程序，打印出讓每個人都滿意的所有分書方案。 張00110 王11001 劉01100 趙00010 錢01001分析：1、樸素的窮舉法：產生5本書的所有全排列，共有5！=120個，逐個檢查各種排列是否符合所有人的要求，符合則輸出，否則丟棄。窮舉法的改進：例如產生一個全排列12345時，第一個數1表示將第一本書給小張。但從表中可以看出，這是不可能的，因為小張只喜歡第三、第四本書。也就是說，X X X X這一類分法是不符合條件的。由此使我們想到，如果選定第一本書后，就立即檢查一下是否符合條件，當發現第一個數的

14、選擇不符合條件時，就不必再產生后面的4個數了，這樣做可以減少很多的運算量。換句話說，第一個數只在3和4中選擇，這樣就可以減少35的運算量。同理，在選定了第一個數后，其他4個數字的選擇也可以用類似的方法處理，即選擇第二個數后，立即檢查是否符合條件。例如，第一個數選3，第二個數選4后，立即進行檢查，發現不符合條件，就另選第二個數。這樣就又把34XXX一類的分法刪去了，從而又減少了一部分運算量。開始張錢趙王劉王劉王張王錢王趙王劉趙王劉張王劉錢王錢張王錢劉王錢趙王劉張趙王劉張錢王錢張趙王錢張劉王錢趙張王錢趙劉王劉張趙錢深搜法：建立如上搜索樹，每一層分發一本書，未向下擴展的結點為當前層已不合理，故剪去。

15、參考程序：program dfs1;const a:array1.5,1.5of boolean=(false,false,true,true,false), (true,true,false,false,true), (false,true,true,false,false), (false,false,false,true,false), (false,true,false,false,true);var outf:text; c:array1.5of integer; hx:array1.5of boolean;/procedure print;var i:integer;begin f

16、or i:=1 to 5 do case ciof 1:write(outf,張); 2:write(outf,王); 3:write(outf,劉); 4:write(outf,趙); 5:write(outf,錢); end;end;/procedure dfs(n:integer);var i:integer;begin for i:=1 to 5 do if (ai,n)and(not(hxi) then begin cn:=i; if n=5 then print; hxi:=true; dfs(n+1); hxi:=false; end;end;/begin assign(outf

17、,dfs_1.out); rewrite(outf); dfs(1); close(outf);end. 例二：跳馬問題:在半張中國象棋盤上（5*9），有一匹馬自左下角往右上角跳，今規定只許往右跳，不許往左跳。編程計算共有多少種不同的跳行路線，并將路線打印出來。 例三：0100001010000000111000010表示一個迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程序找出從左上角到右下角的路線。 例四：有一個m*n的滑雪場，請找出最長的滑雪道。比如：24 40 20 30 28 44 33 35 20 18 30 40 40 35 22 15 13 2

18、0 30 35 25 20 12 18 28 40 30 10 11 20 15 30 12 15 20 12從第一排開始下滑，只能向上、下、左、右四個方向，且下一個區域的高度必須低于當前區域的高度，找出一條滑動距離最長的路徑，可以在任何區域停止。12.4 習題：1、營求（save）【問題描述】鐵達尼號發出了求救信號。距離最近的哥倫比亞號收到了信號，必須盡快趕到那里。通過偵測，哥倫比亞號獲取了一張海洋圖。這張圖將海洋部分分化成nn個比較小的單位，其中用1標明的是陸地，用0標明的是海洋。船只能從一個格子移到相鄰的四個格子。為了盡快趕到出事地點，哥倫比亞號最少需要走多遠的距離。 【輸入格式】第一行

19、為n，下面是一個nn的0，1矩陣，表示海洋地圖。 最后一行為四個小于等于n的整數，分別表示哥倫比亞和鐵達尼號的位置。 【輸出格式】哥倫比亞號到達鐵達尼號的最短距離，答案精確到整數。【輸入樣例】save.in 3 001 101 1001 1 3 3 【輸出樣例】save.out 4 【數據范圍】n=1000 2、硬幣翻轉（coin） 00000000000000*0000000*00*0000000*00*000*000*0*00*0*0*00*00*00*0*000*0000*00000*000000000000【問題描述】在桌面上有一排硬幣，共n枚，每一枚硬幣均為正面向上。現在要把所有的硬

20、幣翻轉成反面向上，規則是每次可翻轉任意n1枚硬幣（正面向上的翻轉成向下，向下的翻轉成向上）。求一個最短的操作序列（將每次翻轉n1枚硬幣定為一次操作）。 【輸入格式】只有一行，包含一個自然數n（n為不大于100的偶數） 【輸出格式】第一行包含一個整數s，表示最少需要的操作次數。接下來s行每行分別表示每次操作后桌上硬幣的狀態（一行包含n個整數（0或1），表示每個硬幣的狀態，0正面向上，1反面向上，不允許出現多余的空格）。對于有多種操作方案的情況，則只需輸出一種。 【輸入樣例】coin.in4 【輸出樣例】coin.out40111110000011111 3、閉合曲線面積(area)【問題描述】編

21、程計算由“*”號圍城的下列圖形的面積。面積計算方法是統計*號所圍城的閉合曲線中水平線和垂直線交點的數目。如下圖所示，在1010的二維數組中，有*圍住了15點，因此面積為15。【輸入樣例】area.in 0000000000000011100000001001000000010010001000101001010100100100110110001000010000011111000000000000【輸出樣例】area.out15 4、細胞（cell） 【問題描述】一矩形陣列由數字09組成，數字19代表細胞，細胞的定義是沿細胞數字上下左右如果還是細胞數字則為同一細胞，求給定矩形陣列的細胞個數。

22、 如陣列： 0234500067 103456050020456006710000000089有4個細胞。 【輸入格式】第一行為整數m，n，接著m行，每行n個數字 【輸出格式】細胞的個數 【輸入樣例】cell.in 4 10 0234500067 1034560500 2045600671 0000000089 【輸出樣例】cell.out 4 5、最少轉彎問題（turn） 【問題描述】給出一張地圖，這張地圖被分為nm（n，mn)，現在允許用量杯從水缸里取水或將水倒回水缸里，而且兩個量杯中的水也可以相互傾倒，試設計計算機程序求出在m升的量杯中準確量得k升(Nknm)所需的最少操作步數。 (每一個取水或倒水都算一個操作步數)【輸入文件】ls.in僅一行，三個數，分別為m,n,k。【輸出文件】ls.out僅一行，為最少步數。【樣例數據】【輸入】4 3 2【輸出】6N8、 所謂蟲食算，就是原先的算式中