深度優(yōu)先搜索

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

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

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

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

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

6、將小張的喜歡的書(shū)改成了 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); 個(gè)人對(duì)各種書(shū)的喜好情況 name:arrayfive of string5 =('zhang', 'wang','liu', 'zhao', 'qian' ); 數(shù)組name存放學(xué)生姓名var book:

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

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

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

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

11、為 3的書(shū)， Like3 ， 3=0 ，表示編號(hào)為 3 的書(shū)是其最后 1 本喜愛(ài)的書(shū)。這樣基本算法不變，但程序改進(jìn)如下：Program allot_book(output); linking Listtype five=1.5;將小張的喜歡的書(shū)改成了 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 ); 個(gè)人對(duì)各種書(shū)的喜好情況 name:arrayfive of string5 =('zhang', 'wa

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

13、booki ) );end;procedure try(i: integer); 判斷第 I 個(gè)學(xué)生分得書(shū)的編號(hào) var j: integer;beginj:=0;repeatj:=linki,j; 取鏈表中喜愛(ài)書(shū)編號(hào) 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)先搜索實(shí)例1【例題2】 電子老鼠闖迷宮。圖中有陰影的部分表示墻，無(wú)陰影的部分表示通 路。老鼠在迷宮中可以沿上下左右4個(gè)方向摸索前進(jìn)。編一程序，由計(jì)算機(jī)自 動(dòng)找到一條從上面入口處到下面出口處的一條通道。 讓計(jì)算機(jī)記住路徑，當(dāng)?shù)?二次走時(shí)，應(yīng)能按路徑較快從入口到達(dá)出口。問(wèn)題分析：(1) 迷宮的表示方法：迷宮一般可以用一個(gè)二維數(shù)組A(Y，X)來(lái)表示，其中，Y表示行，X表示列。數(shù)組中的元素由數(shù)字0和1組成。它們的含義是：/ 1墻A(Y,X)=< 0路設(shè)迷宮入口處的坐標(biāo)為：(1，8)，迷宮出口處的坐標(biāo)為：(10，7)。(2) 搜索

15、方向的識(shí)別：對(duì)于迷宮中的任意一點(diǎn)A(Y，X)，有4個(gè)搜索方向：A(Y-1，X)TA(Y,X- 1) J A(Y,X) A(Y,X+1)A(Y+1，X)(3) 搜索方向的表示方法：我們?cè)O(shè)置一組坐標(biāo)增量來(lái)描述這上下左右4個(gè)搜索方向 (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個(gè)搜索方向。則老鼠向某個(gè)方向試探一步后的新坐標(biāo)應(yīng)表示為：NX=X+DX(I) NY=NY+DY(I)(4) 向某個(gè)方向搜索方法：從上面的分析

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

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

18、 產(chǎn)生規(guī)則。有8條，若用數(shù)組DX和DY表示各方向增量：nx=x+dx(j)；ny=y+dy(j)if (ny ， nx) 是通路 then (ny ， nx) 是新結(jié)點(diǎn)(3) 搜索策略。采用深度優(yōu)先搜索法，即上節(jié)中總結(jié)的算法進(jìn)行搜索。由于 在迷宮探索路程較長(zhǎng)， 搜索深度較大， 用遞歸可能產(chǎn)生溢出， 所以用非遞歸的深 度優(yōu)先算法。程序如下：program labyrinth(output)；uses crt ；type node=record 定義存放行走路徑的記錄類(lèi)型 xx ， yy ： byte ； 位置坐標(biāo) 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); 迷宮布局，為了編程方便，在迷宮的外面四周加了死路標(biāo)記 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 ； 檢查向某方向的探索前進(jìn)是否成功 beginnx : =x+dxj ; 修改X方向坐標(biāo)ny : =y+dyj ； 修改丫方向坐標(biāo)if (nx<1) or (nx>11) or (ny<1) or (ny>11) 超出迷宮邊界 then check:=false ch

22、eck 為假，表示此方向搜索前進(jìn)失敗 else if any,nx>0 then check:=false 前方為墻或死路 else check:=true； 此搜索方向可行 end ；procedure backtrack; 回溯，返回上一步 beginrepeatdec(dep);返回上一步，將搜索深度減 1 if dep = 0then t7: = trueelseheginay,x: =2;置死路標(biāo)記 gotoxy(x+1,y+1) ;write(chr(176); 打印后退標(biāo)記“圈”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) ); 打印行走成功標(biāo)記“曰”gotoxy(1,15);wri re( 'see you again(y/n) :'); readln(ch);if (ch='y') or (ch='Y') then 重走迷宮時(shí)處理 beginclrscr ;display(b);

24、 打印迷宮初始布局 for i: = 1 to dep do with pathi dobegin gotoxy(xx + 1, yy + 1) ;write(chr(219) ); 根據(jù)數(shù)組 Path 中記錄的行走路線(xiàn)，走出迷宮路線(xiàn) wait; end;gotoxy(1,20); write( 'end !' ); readln end;haltend; main prg beginy0: = 10; x0: =7; b:=a; clrser; display(a);dep: = 1;迷宮出口坐標(biāo) 保存迷宮初始布局 with path1 do 初始化，設(shè)置迷宮入口情況 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;搜索前進(jìn)方向 某方向搜索前進(jìn)成功 將來(lái)路設(shè)為死路，避免老鼠在迷，宮中原地記錄前進(jìn)方向 改坐標(biāo)，前進(jìn)一步

26、 end;達(dá)迷宮出口 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ī)定，老鼠在迷宮中的行走方向?yàn)樯舷伦笥?4 個(gè)方向， 如果將老鼠在迷宮中可摸索前進(jìn)的方向擴(kuò)充為 8 個(gè)，即除了可以沿上下左右 4 個(gè)方向摸索前進(jìn)外，還可以沿左上、右上、左下、右下 4 個(gè)方向摸索前進(jìn)，上述 程序應(yīng)如何修改，請(qǐng)同學(xué)們自己試一試。1 2 深度優(yōu)先搜索實(shí)例 2【例題 3】 騎士周游世界。在國(guó)際象

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