算法與數(shù)據(jù)結(jié)構(gòu)講義三（搜索算法）

1、第十三課 搜索算法12.0 搜索樹12.1 搜索算法的基本原理12.2 廣度優(yōu)先搜索12.3 深度優(yōu)先搜索12.4 練習(xí)12.0 搜索樹引例：在一個4*4的棋盤上的左下角有一個馬，按照國際象棋的規(guī)則，將這個馬跳到右*上角。分析：首先建立棋盤的坐標(biāo)，我們以左下角為(1,1)，以右上角、為(4,4)。按照馬的移動規(guī)則，假定當(dāng)前馬的位置坐標(biāo)為(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)兩個點(其它移動規(guī)則由于邊界限制無法到達(dá))；(2,3)又可以跳到(1,1)、(4,4)、(4,2)、(3,1)四個點，(3,2)可以跳達(dá)(1,1)、(1,3)、(2,4)、(4,4)四個點，。搜索樹：按照數(shù)據(jù)元素的產(chǎn)生式規(guī)則建立起來的數(shù)據(jù)元素邏輯關(guān)系。特點：（1）數(shù)據(jù)之間的邏輯關(guān)系為一對多。 （2）每個結(jié)點數(shù)據(jù)的下一級子結(jié)點是由該結(jié)點的產(chǎn)生式規(guī)則生成。 （3）目標(biāo)結(jié)點（答案數(shù)據(jù)）一定在搜索樹中能夠出現(xiàn)

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

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

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

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

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

8、結(jié)點回朔，用一個棧存儲回朔的中間狀態(tài)。例二：在一個2n+1的一維棋盤上，有n個黑色棋子和n個白色棋子，初始狀態(tài)如圖：規(guī)定棋子移動規(guī)則如下：如果某棋子的旁邊正好為空，這枚棋子可以移動到空位置上。如果某棋子的一側(cè)有棋子，二那枚棋子的另一側(cè)為空位置，這枚棋子可以跳過那枚棋子到空位置上。問：最少經(jīng)過多少步，可以將棋盤狀態(tài)變成分析：用2n+1位三進(jìn)制數(shù)表示狀態(tài)，如初始狀態(tài)為：222201111，目標(biāo)狀態(tài)為111102222。轉(zhuǎn)化為十進(jìn)制進(jìn)行存儲，另記錄空格位置。產(chǎn)生式規(guī)則：將棋子移動轉(zhuǎn)化為空格的移動?？崭裣蜃笠苿涌崭裣蛴乙苿涌崭裣蜃筇鴦涌崭裣蛴姨鴦佑靡粋€1.32n+1的哈希數(shù)組判重。例三：八數(shù)碼問題。在

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

10、的結(jié)點還有以此為根的下一層結(jié)點，則沿此路繼續(xù)下去，直到無法再深入訪問時，回朔到上一層的結(jié)點，選另一條路繼續(xù)深入訪問。反復(fù)此過程，直到所有結(jié)點都被訪問到為止。算法過程：首先將根結(jié)點放入棧中。取出棧頂結(jié)點，按照產(chǎn)生式規(guī)則生成新的結(jié)點數(shù)據(jù)，每產(chǎn)生一個：檢查是否是目標(biāo)結(jié)點，如果是且比保存的數(shù)據(jù)更優(yōu)，刷新所保存的數(shù)據(jù)。檢查該結(jié)點是否已搜過，如果是且比已保存的數(shù)據(jù)更優(yōu)，則刷新所保存的數(shù)據(jù)，然后該結(jié)點進(jìn)棧；如沒有搜過，則保存數(shù)據(jù)并進(jìn)棧。轉(zhuǎn)第二步。如果?？?，則算法結(jié)束。細(xì)化說明：一般用回朔法，利用遞歸使用系統(tǒng)棧。哈希數(shù)組不僅用于判斷新結(jié)點是否出現(xiàn)過，還用于保存到達(dá)該結(jié)點時的中間數(shù)據(jù)。算法框架：procedur

11、e dfs(結(jié)點數(shù)據(jù));var i:integer;begin for i:=產(chǎn)生式規(guī)則一 to 最大產(chǎn)生式規(guī)則 do begin 新結(jié)點數(shù)據(jù):=creat(i); if (新結(jié)點數(shù)據(jù)沒有搜到過)or(新結(jié)點數(shù)據(jù)雖已搜過但本次搜索結(jié)果更優(yōu)) then begin更新新結(jié)點搜索結(jié)果;dfs(新結(jié)點數(shù)據(jù)); end;end;procedure dfs(結(jié)點數(shù)據(jù));var i:longint;beginfor i:=1 to 最大產(chǎn)生式規(guī)則 dobegin新結(jié)點:=creat(i);if 新結(jié)點是目標(biāo)結(jié)點 thenbegin傳回新結(jié)點;t:=true;exit;end;if 新結(jié)點更優(yōu) thenbe

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

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

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

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），有一匹馬自左下角往右上角跳，今規(guī)定只許往右跳，不許往左跳。編程計算共有多少種不同的跳行路線，并將路線打印出來。 例三：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從第一排開始下滑，只能向上、下、左、右四個方向，且下一個區(qū)域的高度必須低于當(dāng)前區(qū)域的高度，找出一條滑動距離最長的路徑，可以在任何區(qū)域停止。12.4 習(xí)題：1、營求（save）【問題描述】鐵達(dá)尼號發(fā)出了求救信號。距離最近的哥倫比亞號收到了信號，必須盡快趕到那里。通過偵測，哥倫比亞號獲取了一張海洋圖。這張圖將海洋部分分化成nn個比較小的單位，其中用1標(biāo)明的是陸地，用0標(biāo)明的是海洋。船只能從一個格子移到相鄰的四個格子。為了盡快趕到出事地點，哥倫比亞號最少需要走多遠(yuǎn)的距離。 【輸入格式】第一行

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

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

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

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