深度優(yōu)先搜索

1、1 深度優(yōu)先搜索 DFS我們在對一些問題進行求解時， 會發(fā)現(xiàn)有些問題很難找到規(guī)律， 或者根本無規(guī)律 可尋。對于這樣的問題， 可以利用計算機運算速度快的特點， 先搜索查找所有可 能出現(xiàn)的情況，再根據(jù)題目條件從所有可能的情況中， 刪除那些不符合條件的解?！纠} 1】 有 A、B、C、D、E 5 本書，要分給張、王、劉、趙、錢 5位同學， 每人只能選 1 本。每個人都將自己喜愛的書填寫在下表中。請你設計一個程序， 打印出讓每個人都滿意的所有分書方案。I B | C | D | E0011011001011000001001001問題分析題目中每人喜愛哪本書是隨意的， 無規(guī)律可循，所以用窮舉方法解較為

2、合適。 按窮舉法的一般算法， 可以暫不考慮一些條件， 先求出滿足部分條件的解， 即可 行解。然后，再加上尚未考慮的條件，從可行解中刪除不符合這些條件的解，留 下的就是問題的解。 具體到本題中， 我們可以先不考慮“讓每人都滿意”這個條 件，這樣，就只?！懊咳诉x一本且只能選一本”這一個條件了。在這個條件下， 可行解是 5本書的所有全排列，一共有 5!=120 種情況。從這 120種可行解中刪 去不符合“每人都滿意”這一條件的解，剩下的就是本題的解。為編程方便，我們用 1、2、3、4、5 分別表示這 5 本書。這 5 個數(shù)字的種 全排列就是5本書的一種分法。例如54321就表示第五本書（即E）分給張

3、，第四 本書（即D）分給王”，第一本書 （即A）分給錢。每個人“喜愛書表”，在程序中我們用二維數(shù)組 Likei,j 來表示， 1 表示 喜愛， 0 表示不喜愛。排列的產(chǎn)生可以用窮舉法，也可以用專門算法。算法設計：第一步：產(chǎn)生 5 個數(shù)字的一個全排列；第二步：檢查所產(chǎn)生的全排列是否符合“喜愛書表”，如果符合就輸出；第三步：檢查是否所有排列都產(chǎn)生了，如果沒有產(chǎn)生完，則返回第一步；第四步：結(jié)束。根據(jù)題目給出的條件， 還可以對上面算法進行一些改進。 例如產(chǎn)生一個全排 列 12345 時，第一個數(shù) 1 表示將第一本書給小張。 但從表中可以看出， 這是不可 能的，因為小張只喜歡第三、第四本書。也就是說，1

4、 XXXX這一類分法是不 符合條件的。 由此使我們想到， 如果選定第一本書后， 就立即檢查一下是否符合 條件，當發(fā)現(xiàn)第一個數(shù)的選擇不符合條件時， 就不必再產(chǎn)生后面的 4 個數(shù)了， 這 樣做可以減少很多的運算量。 換句話說， 第一個數(shù)只在 3 和 4 中選擇， 這樣就可 以減少 35 的運算量。同理，在選定了第一個數(shù)后，其他 4個數(shù)字的選擇也可 以用類似的方法處理，即選擇第二個數(shù)后，立即檢查是否符合條件。例如，第一 個數(shù)選 3，第二個數(shù)選 4 后，立即進行檢查， 發(fā)現(xiàn)不符合條件， 就另選第二個數(shù)。 這樣就又把34XXX 類的分法刪去了，從而又減少了一部分運算量。綜上所述，改進后本題算法應該是：在

5、產(chǎn)生各種排列時，每增加一個數(shù)字， 就檢查一下該數(shù)的加入是否符合條件，如不符合，就立刻換一個；若符合條件， 則再產(chǎn)生下一個數(shù)。 因為從第 i 本書到第 i+1 本書的尋找過程是相同的， 所以可 以用遞歸方法編程。算法框圖PROCEDURE TRY；(i)( 遞歸算法 )For j:= 1 to 5 do1 1TI 個學生喜愛第 ji1Fii= 5TF丨丨1 1Try(i+1)i11我們用二維數(shù)組 like 存放 “喜愛書表 ”，用集合 flag 存放已分出書的編號，數(shù)組 book 存儲 各人所分得書的編號，如 book1=3 ，則表示第一個同學 (小張)分得編號為 3的書。遞歸程序如下 (程序中

6、將小張的喜歡的書改成了 ACD) ：Program allot_book(output);type five=1.5;const like: arrayfive,five of 0.1 =(1, 0, 1,1 ,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1); 個人對各種書的喜好情況 name:arrayfive of string5 =('zhang', 'wang','liu', 'zhao', 'qian' ); 數(shù)組name存放學生姓名var book:

7、 array1.5 of 0.5;存放各人分配到的書的編號 flag: set of five;c: integer;procedure print; 打印分配方案 var i: integer;begininc(c); 計數(shù)，統(tǒng)計得到分配方案數(shù) writeln( 'answer', c,':');for i:=1 to 5 dowriteln(namei: 10,':', chr(64 + booki ) );end;procedure try(i: integer); 判斷第 I 個學生分得書的編號 var j: integer;beginf

8、or j:=1 to 5 doif not(j in flag) and (likei,j>0) thenbegin 第 j 本書未選過，且第 I 個學生喜愛第 j 本書 flag:= flag + j; 修改已選書編號集合，加入第 j 本書 booki:=j; 記錄第 I 個學生分得書的編號 if i= 5 then print I = 5,5個學生都分到自己喜愛的書 else try(i + 1);i<5, 繼續(xù)搜索下一個學生可能分到書的情況 flag:= flag - j; 后退一步，以便查找下一種分配方案 booki:=0;endend; main prg beginfla

9、g:= ;c:=0;try(1);readlnend.運行結(jié)果為 :zhang: Cwang: Aliu:BZhao: Dqian: E 另外，此題也可以用非遞歸的算法解。非遞歸算法的基本思想是用棧來存放被選中書的 編號。設 dep 表示搜索深度， r 為待選書號， p 為搜索成功標志。算法表示如下(非遞歸算 法)。PROCEDURE dfs（非遞歸算法）Dep:=0dep:=dep+1j:=0; p:=Falsej:=j+1T mr FT Mxar FFP:=Fatse |P:= trueUNTIL p=TrueUNTIL dep= 0盡管深度優(yōu)先基本算法類似，但在處理不同問題時，在具體處理

10、方法、編程的技巧上， 卻不盡相同；有時甚至會有很大的差別。比如，例 1 的解法還可以這樣來設計：從表中看出，趙同學只喜愛 D 這一本書，無其它 選擇余地。 因此，趙同學得到書的編號在搜索前就確定下來了。為了編程方便，可以把趙錢 2 人位置交換，這樣程序只需對張王劉錢 4 人情況進行搜索測試。另外，發(fā)現(xiàn)表示 “喜愛書表 ”的數(shù)組有多個 0，為減少不必要的試探， 我們改用鏈表來表示。 例如第三位同學的鏈表是： Like3 ，0=2.Like3 ， 2=3.Like3 ， 3=0 ，其中， Like3 ，0=2 表示他喜愛的第一本書編號是2，Like3 ，2=3 即表示喜愛的編號為 2的書后面是編號

11、為 3的書， Like3 ， 3=0 ，表示編號為 3 的書是其最后 1 本喜愛的書。這樣基本算法不變，但程序改進如下：Program allot_book(output); linking Listtype five=1.5;將小張的喜歡的書改成了 ACDconst Link: Array 1.5,0.5 of 0.5 = (1,3,0,4,0,0),(1,2,5,0,0,0),(2,0,3,0,0,0),(4,0,0,0,0,0),(2,0,5,0,0,0 ); 個人對各種書的喜好情況 name:arrayfive of string5 =('zhang', 'wa

12、ng','liu', 'zhao', 'qian' );數(shù)組name存放學生姓名var book: array1.5 of 0.5;存放各人分配到的書的編號 flag: set of five;c: integer;procedure print; 打印分配方案 var i: integer;begininc(c); 計數(shù)，統(tǒng)計得到分配方案數(shù) writeln( 'answer', c,':');for i:=1 to 5 do writeln(namei: 10,':', chr(64 +

13、booki ) );end;procedure try(i: integer); 判斷第 I 個學生分得書的編號 var j: integer;beginj:=0;repeatj:=linki,j; 取鏈表中喜愛書編號 j If not(j in flag) and (j>0) thenBegin flag:= flag+ j; booki:=j; if i=5 then print else try(i + 1);flag:= flag - j; 后退一步，以便查找下一種分配方案 booki:=0;End;until j = 0;end; main prg beginflag:= ;c

14、:=0;try(1);readlnend.§ 1 2深度優(yōu)先搜索實例1【例題2】 電子老鼠闖迷宮。圖中有陰影的部分表示墻，無陰影的部分表示通 路。老鼠在迷宮中可以沿上下左右4個方向摸索前進。編一程序，由計算機自 動找到一條從上面入口處到下面出口處的一條通道。 讓計算機記住路徑，當?shù)?二次走時，應能按路徑較快從入口到達出口。問題分析：(1) 迷宮的表示方法：迷宮一般可以用一個二維數(shù)組A(Y，X)來表示，其中，Y表示行，X表示列。數(shù)組中的元素由數(shù)字0和1組成。它們的含義是：/ 1墻A(Y,X)=< 0路設迷宮入口處的坐標為：(1，8)，迷宮出口處的坐標為：(10，7)。(2) 搜索

15、方向的識別：對于迷宮中的任意一點A(Y，X)，有4個搜索方向：A(Y-1，X)TA(Y,X- 1) J A(Y,X) A(Y,X+1)A(Y+1，X)(3) 搜索方向的表示方法：我們設置一組坐標增量來描述這上下左右4個搜索方向 (0，1)表示向右：(X增1) (-1，0)表示向上：(Y減1) (0，-1)表示向左：(X減1) (1，0)表示向下：(Y增1)在程序中表示為，X方向增量為DX(I),Y方向增量為DY(I)，I的取值為1, 2, 3, 4,表示4個搜索方向。則老鼠向某個方向試探一步后的新坐標應表示為：NX=X+DX(I) NY=NY+DY(I)(4) 向某個方向搜索方法：從上面的分析

16、中看到，向某方向搜索前進一步的處理，只需在當前位置坐標，加上搜索方向的坐標增量DX(i)和DY(i)。但修改位置坐標后一定要注意：任何一點的坐標加上要搜索方向的坐標增量之后，都要 判斷一下是否已超出了迷宮的邊界。凡是 X<0,或x>10,或丫<0,或丫>10的情 況，均表示新的位置坐標已超出了迷宮的邊界。 這時， 就應放棄向該方向搜索移 動,改為向下一個方向探索前進。另外，在不超出迷宮邊界的情況下，如果A(Y, X)=0，則表示該方向有通路， 可以繼續(xù)向前走，若A(Y，X)=1，則表示該方向是墻，不能前行。(5) 為了防止老鼠在迷宮中誤入歧途并在原地打轉(zhuǎn)，當老鼠從某條死

17、胡同中退回時，應把該路堵死。要實現(xiàn)這一點很容易，只需使A(Y，X)=2，將已走過的路的標志設為死路標志即可。(6) 為了能記住走出迷宮的路徑，在搜索過程中還要建立一個堆棧，將老鼠 走過的每一步路都記錄下來， 當老鼠碰壁后退時， 就將退出的路從堆棧中彈出去。 這樣，最終堆棧中保存的就是走出迷宮的一條通路了。 這時棧底元素為迷宮的入 口處坐標，棧頂元素是迷宮的出口處坐標。產(chǎn)生式系統(tǒng) ：(1) 數(shù)據(jù)庫。要存儲老鼠在迷宮中走過的路，那么每個記錄需要有：行、列坐標，搜索方向 3 個數(shù)據(jù)；根據(jù)以上分析， 數(shù)據(jù)庫應組成堆棧形式， 用數(shù)組 path 表示，并用變量DEP乍為棧頂指針，同時表示搜索的深度。(2)

18、 產(chǎn)生規(guī)則。有8條，若用數(shù)組DX和DY表示各方向增量：nx=x+dx(j)；ny=y+dy(j)if (ny ， nx) 是通路 then (ny ， nx) 是新結(jié)點(3) 搜索策略。采用深度優(yōu)先搜索法，即上節(jié)中總結(jié)的算法進行搜索。由于 在迷宮探索路程較長， 搜索深度較大， 用遞歸可能產(chǎn)生溢出， 所以用非遞歸的深 度優(yōu)先算法。程序如下：program labyrinth(output)；uses crt ；type node=record 定義存放行走路徑的記錄類型 xx ， yy ： byte ； 位置坐標 r ： byte 搜索方向 end ；a11=array0.11， 0.11 of

19、 byte；const dx ： array1.4 of integer=(0， 1 ， 0， -1) ；X 方向增量 dy ： array1.4 of integer=(1， 0， -1 ， 0) ；Y 方向增量 a ： a11=(1,1,1,1,1,1,1,1,1,1,1,1),(1,0,0,0,0,0,0,1,0,1,1,1),(1,0,1,0,1,1,0,0,0,0,0,1),(1,0,1,0,1,1,0,1,1,1,0,1),(1,0,1,0,0,0,0,0,1,0,0,1),(1,0,1,1,1,1,1,1,1,1,1,1),(1,0,0,0,1,0,1,0,0,0,0,1),(1

20、,0,1,1,1,0,0,0,1,1,1,1),(1,O,O,O,O,O,1,O,O,O,O,1),(1,1,1,O,1,1,1,1,0,1,O,1),(1,1,1,1,1,1,1,1,0,1,1,1),(1,1,1,1,1,1,1,1,1,1,1,1); 迷宮布局，為了編程方便，在迷宮的外面四周加了死路標記 varb ： all ；dep ， j ， k， x， y， xo， yo， nx， ny： integer ；path ： array0.300 of node；p ： boolean ；procedure wait ；begin for k ： =1 to 5000 do end ；

21、procedure display(a ：a11) ； 打印迷宮布局 var i ， j ：byte ；beginfOr i ： =0 to 11 dobeginfor j ： =0 to 11 do write(ai,j)；writeln endend ；function check ：bcxolean ； 檢查向某方向的探索前進是否成功 beginnx : =x+dxj ; 修改X方向坐標ny : =y+dyj ； 修改丫方向坐標if (nx<1) or (nx>11) or (ny<1) or (ny>11) 超出迷宮邊界 then check:=false ch

22、eck 為假，表示此方向搜索前進失敗 else if any,nx>0 then check:=false 前方為墻或死路 else check:=true； 此搜索方向可行 end ；procedure backtrack; 回溯，返回上一步 beginrepeatdec(dep);返回上一步，將搜索深度減 1 if dep = 0then t7: = trueelseheginay,x: =2;置死路標記 gotoxy(x+1,y+1) ;write(chr(176); 打印后退標記“圈”wait;x:= pathdep.xx; 棧頂元素出棧 1y:= pathdep.yy;j:=

23、pathdep.rend;until (dep=O) or (j<4);end;procedure print(dep: integer);var i, k: integer;ch: char;begingotoxy(nx + 1, ny + 1) ;write(chr(219) ); 打印行走成功標記“曰”gotoxy(1,15);wri re( 'see you again(y/n) :'); readln(ch);if (ch='y') or (ch='Y') then 重走迷宮時處理 beginclrscr ;display(b);

24、 打印迷宮初始布局 for i: = 1 to dep do with pathi dobegin gotoxy(xx + 1, yy + 1) ;write(chr(219) ); 根據(jù)數(shù)組 Path 中記錄的行走路線，走出迷宮路線 wait; end;gotoxy(1,20); write( 'end !' ); readln end;haltend; main prg beginy0: = 10; x0: =7; b:=a; clrser; display(a);dep: = 1;迷宮出口坐標 保存迷宮初始布局 with path1 do 初始化，設置迷宮入口情況 beg

25、in xx: =8;yy: = 1 end;repeat取棧頂元素 with pathdep do begin x: =xx;y: =yy end;j: =0;p:=false; repeat inc(j); if check then begin ay,x:= 1; 打轉(zhuǎn) pathdep, r: =j; inc(dep); with pathdep do begin xx:= nx;yy:=ny; gotoxy( x + 1, y + 1 ); write(chr(219) ); wait;搜索前進方向 某方向搜索前進成功 將來路設為死路，避免老鼠在迷，宮中原地記錄前進方向 改坐標，前進一步

26、 end;達迷宮出口 if (nx=x0) and (ny= y0) then print(dep) else p: = true;endelseif j >= 4 then backtrack;until p = true;until dep=0;readlnend.想一想：上面題目中規(guī)定，老鼠在迷宮中的行走方向為上下左右 4 個方向， 如果將老鼠在迷宮中可摸索前進的方向擴充為 8 個，即除了可以沿上下左右 4 個方向摸索前進外，還可以沿左上、右上、左下、右下 4 個方向摸索前進，上述 程序應如何修改，請同學們自己試一試。1 2 深度優(yōu)先搜索實例 2【例題 3】 騎士周游世界。在國際象

27、棋的棋盤上，有一位騎士按照國際象棋中 馬的行走規(guī)則從棋盤上的某一方格出發(fā)， 開始在棋盤上周游。 若能不重復地走遍 棋盤上的每一個方格， 這樣的一條周游路線在數(shù)學上被稱之為國際象棋盤上馬的 哈密爾頓鏈。請你設計一個程序，對于從鍵盤輸入的任意一個起始方格的坐標， 由計算機自動尋找并按如下格式打印出國際象棋盤上馬的哈密爾頓鏈。 例如，當 馬從坐標點 (5，8) 出發(fā)時，相應的哈密爾頓鏈如下圖所示：1 1601 1111126129211541131 1241r271Ir r30r r61r r12rr25rrrr221 1511I14r10r r59r r28rr55rr50rrrr531I20II23rr31r r64r r57rr62rr43rrrr4815II52rr58r rr r32r r491rr56rrrr1942IIrr33r rr r63rr44rr47rrrr3639