程序設(shè)計：深度優(yōu)先搜索算法

1、深度優(yōu)先搜索算法教程例1 有A、B、C、D、E五本書，要分給張、王、劉、趙、錢五位同學(xué)，每人只能選一本。事先讓每個人將自己喜愛的書填寫在下表中。希望你設(shè)計一個程序，打印分書的所有可能方案，當(dāng)然是讓每個人都滿意。（如下圖所示）分析 這個問題中喜愛的書是隨機(jī)的，沒有什么規(guī)律，所以用窮舉法比較合適。為編程方便，用1、2、3、4、5分別表示這五本書。這五本書的一種全排列就是五本書的一種分法。例如54321表示第5本書（即E）分給張，第4本書（即D分給王，）第1本書（即A分給錢）?！跋矏蹠怼笨梢杂枚S數(shù)組來表示，1表示喜愛，0表示不喜愛。算法設(shè)計：1、 產(chǎn)生5個數(shù)字的一個全排列；2、 檢查是否符合“喜

2、愛書表”的條件，如果符合就打印出來。3、 檢查是否所有排列都產(chǎn)生了，如果沒有產(chǎn)生完，則返回1。4、 結(jié)束。算法改進(jìn)：因?yàn)閺堉幌矚g第3、4本書，這就是說，1* * * *一類的分法都不符合條件。所以改進(jìn)后的算法應(yīng)當(dāng)是：在產(chǎn)生排列時，每增加一個數(shù)，就檢查該數(shù)是否符合條件，不符合，就立即換一個，符合條件后，再產(chǎn)生下一個數(shù)。因?yàn)閺牡趇本書到第i+1本書的尋找過程是相同的，所以可以用遞歸算法。算法如下：procedure try(i); 給第I個同學(xué)發(fā)書begin for j:=1 to 5 dobeginif 第i個同學(xué)分給第j本書符合條件 then begin記錄第i個數(shù); 即j值if i=5 th

3、en 打印一個解 else try(i+1);刪去第i個數(shù)字endendend;具體如下：遞歸算法program zhaoshu;const like:array1.5,1.5 of 0.1 =(0,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:array1.5 of string5 =('zhang','wang','liu','zhao','qian');var book:array1.5 of 0.5; flag:set of 1

4、.5; c:integer;procedure print; var i:integer; begin inc(c); writeln('answer',c,':'); for i:=1 to 5 do writeln(namei:10,':',chr(64+booki); end;procedure try(i:integer);var j:integer;begin for j:=1 to 5 do if not(j in flag) and (likei,j>0) then begin flag:=flag+j; booki:=j;

5、if i=5 then print else try(i+1); flag:=flag-j; booki:=0; end;end;=main=begin flag:=; c:=0; try(1); readln;end.C語言代碼：#include<stdio.h>#include<stdlib.h>int like55=0,0,1,1,0,1,1,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,0,0,1;char name510="zhang","wang","liu","zhao&q

6、uot;,"qian"int flag5=1,1,1,1,1;int book5,c=0;void print() int i; c+; printf("answer %d:",c); for(i=0;i<=4;i+) printf("%s:%c ",namei,65+booki); printf("n");void dsf(int i) int j; for(j=0;j<=4;j+) if(flagj&&likeij) flagj=0;booki=j; if(i=4) print();

7、 else dsf(i+1); flagj=1;booki=0; int main() dsf(0); system("pause"); return 0; 非遞歸算法program path;dep:=0; dep為棧指針，也代表層次repeat dep:=dep+1; r:=0; p:=false; repeat r:=r+1;if 子節(jié)點(diǎn)mr符合條件 then 產(chǎn)生新節(jié)點(diǎn)并存于dep指向的棧頂； if 子節(jié)點(diǎn)是目標(biāo) then 輸出并退出（或退棧） else p:=true;else if r>=maxr then 回溯 else p:=flase; e

8、ndif;until p:=true;until dep=0;其中回溯過程如下：procedure 回溯； dep:=dep-1; if dep=0 then p:=true else 取回棧頂元素（出棧）；具體如下：非遞歸算法program zhaoshu2;uses crt;const like:array1.5,1.5 of 0.1 =(0,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:array1.5 of string5 =('zhang','wang','liu&

9、#39;,'zhao','qian');var book:array0.5 of 0.5; flag:set of 1.5; c,dep,r:longint; p:boolean;f:text;procedure print; var i:integer; begin inc(c); writeln(f,'answer',c,':'); for i:=1 to 5 do writeln(f,namei:10,':',chr(64+booki); end;procedure back;begin dep:=dep-1

10、; if dep=0 then p:=true else begin r:=bookdep; flag:=flag-r; end;end;=main=begin assign(f,'d:wuren.pas'); rewrite(f); clrscr; flag:=; c:=0; dep:=0; repeat dep:=dep+1; r:=0; p:=false; repeat r:=r+1; if not(r in flag) and (likedep,r>0)and (r<=5)then begin flag:=flag+r; bookdep:=r; if dep

11、=5 then begin print;inc(dep);back; end else p:=true; end else if r>=5 then back else p:=false until p=true; until dep=0; close(f);end.上述程序運(yùn)行產(chǎn)生結(jié)點(diǎn)的過程如下圖所示： 結(jié)點(diǎn)旁的編號是結(jié)點(diǎn)產(chǎn)生的先后順序。從產(chǎn)生的順序可以看出，深度越大的結(jié)點(diǎn)越先進(jìn)行擴(kuò)展，即先產(chǎn)生它的子結(jié)點(diǎn)。例如，有了結(jié)點(diǎn)（3）和（31）后，并不是繼續(xù)產(chǎn)生（3）的子結(jié)點(diǎn)，而是先產(chǎn)生（31）的子結(jié)點(diǎn)（312）。這是由于（31）的深度是2，（3）的深度是1，（31）的深度大，所以先

12、擴(kuò)展。同前邊圖的深度優(yōu)先遍歷聯(lián)系起來這種在搜索過程中，深度大的節(jié)點(diǎn)先進(jìn)行擴(kuò)展的算法，稱之為深度優(yōu)先搜索法。簡稱DFS法。（Depth_First_Search）。深度優(yōu)先搜索的特點(diǎn)：(1) 對已產(chǎn)生的節(jié)點(diǎn)按深度排序,深度大的先得到擴(kuò)展，即先產(chǎn)生它的子節(jié)點(diǎn)。(2) 深度大的節(jié)點(diǎn)是后產(chǎn)生的，但先得到擴(kuò)展，即“后產(chǎn)生，先擴(kuò)展”，因此，采用堆棧作為該算法的數(shù)據(jù)結(jié)構(gòu)。深度優(yōu)先搜索的基本思想：1、把初始狀態(tài)賦到state(1)中，即初狀態(tài)入棧，并初始化指針1>object, 1>top。（注釋：state(x)表示節(jié)點(diǎn)x的狀態(tài)，state(1)表示初始狀態(tài)，object表示作擴(kuò)展的節(jié)點(diǎn)。Top

13、表示由節(jié)點(diǎn)object擴(kuò)展的子節(jié)點(diǎn)。）2、分別用waymax種途徑擴(kuò)展object的子節(jié)點(diǎn)。 (1)從途徑1開始擴(kuò)展新節(jié)點(diǎn) 1>waynum。（注釋：waymax表示所有可能擴(kuò)展子節(jié)點(diǎn)的途徑的總數(shù)目，waynum表示所選途徑編號） （2）判斷waynum途徑可行嗎？（即可否擴(kuò)展新節(jié)點(diǎn)）若不行，轉(zhuǎn)2（5）。 （3）對新節(jié)點(diǎn)設(shè)父指針，新狀態(tài)入棧。top+1>top，object>father(top)，state(object)經(jīng)途徑waynum改變后的新狀態(tài)>state(top)中。(注釋：father(x)節(jié)點(diǎn)x 的父節(jié)點(diǎn)的標(biāo)號。) （4）top是目標(biāo)節(jié)點(diǎn)嗎？是，則調(diào)用

14、打印結(jié)果子程序print打印結(jié)果路徑。若只要求一個方案則結(jié)束，否則，讓節(jié)點(diǎn)top出棧再繼續(xù)執(zhí)行下一步。 （5）選擇下一條路徑，即waynum+1>waynum，若waynum<=waymax，則轉(zhuǎn)2(2)。3、選擇用來擴(kuò)展的新節(jié)點(diǎn)。 （1）若object<top，（即object有子節(jié)點(diǎn)）則轉(zhuǎn)3(3)。 （2）top出棧，top-1>top，若top=0（?？談t結(jié)束），若top已擴(kuò)展，再轉(zhuǎn)3(2)。 （3）top>object，若object已規(guī)定深度，則轉(zhuǎn)3(2)。否則轉(zhuǎn)2(1)。深度優(yōu)先搜索Pascal語言程序：program dfs(input,output

15、);const n=擴(kuò)展節(jié)點(diǎn)估計數(shù)；waymax=擴(kuò)展節(jié)點(diǎn)途徑數(shù)；var state, father：array1.n of integer;top, object, waynum：integer;procedure print(v：integer);beginwhile v>0 dobegin write(statev, '<='); v：=fathervend;end;begin(第一步)state1：=初狀態(tài)；object： =1；top:=1; father1:=0;while top>0 dobeginfor waynum:=1 to waymax

16、do （第二步） begin if way(maxnum) 可行 then begin top:=top+1; fathertop:=object; statetop:=新狀態(tài)； if top 是目標(biāo)節(jié)點(diǎn) then begin print(top); top:=top-1; end; end; end; if top>object then object:=top（第三步）else repeat top:=top-1; object:=top until top<>fathertop+1;end;end.深度優(yōu)先搜索的基本算法如下：一、遞歸算法遞歸過程為：procedure

17、DFS_TRY(i);for r:=1 to maxr do if 子結(jié)點(diǎn)mr符號條件 then 產(chǎn)生的子結(jié)點(diǎn)mr壓入棧； if 子結(jié)點(diǎn)mr是目標(biāo)結(jié)點(diǎn) THEN 輸出 ELSE DFS_TRY（I+1）；棧頂元素出棧（刪去mr）;ENDIF；ENDDO；主程序?yàn)椋篜ROGRAM DFS；初始狀態(tài)入棧；DFS_TRY（1）；二、非遞歸算法：PROGRAM DFS（DEP）；DEP：=0；REPEAT DEP：=DEP+1；J：=0；P：=FALSE；REPEAT J：=J+1；IF MR 符合條件 THEN產(chǎn)生子結(jié)點(diǎn)MR并將其記錄；IF 子結(jié)點(diǎn)是目標(biāo) THEN 輸出并出棧 ELSE P：=TRU

18、E；ELSE IF J>=MAXJ THEN回溯 ELSE P：=FALSE；ENDIF；UNTIL P=TRUE；UNTIL DEP=0；其中回溯過程如下：PROCEDURE BACKTRACKING；DEP：=DEP-1；IF DEP>0 THEN 取回棧頂元素 ELSE P：=TRUE；不同問題的深度優(yōu)先搜索基本算法是一樣的，但在具體處理方法上，編程的技巧上，不盡相同，甚至?xí)泻艽蟛顒e。比如例1的解法還可以這樣來設(shè)計：從表中看出，趙同學(xué)只喜愛D一本書，無其他選擇余地。因此可以在搜索前就確定下來。為了編程方便，把趙錢二人位置互換，這樣程序只需對張王劉錢四人進(jìn)行搜索。另外，發(fā)現(xiàn)表

19、示“喜愛書表”的數(shù)組有多個0，為減少不必要的試探，我們改用鏈表來表示。例如第3位同學(xué)的鏈表是：LIKE（3，0）=2，表示他喜愛的第一本書編號是3，最后LIKE（3，3）=0，表示3是最后一本喜愛的書。深度優(yōu)先搜索算法小結(jié) 1可以用深度優(yōu)先搜索法處理的問題是各種各樣的。有的搜索深度是已知和固定的，有的是未知的，有的搜索深度是有限制的，但達(dá)到目標(biāo)的深度不定，但我們也看到，無論問題的內(nèi)容、性質(zhì)、求解要求如何不同，但它們的程序結(jié)構(gòu)都是相同的，即都是第四節(jié)中描述的算法結(jié)構(gòu)，不相同的僅僅是存儲結(jié)點(diǎn)的數(shù)據(jù)庫結(jié)構(gòu)、產(chǎn)生規(guī)則和輸出要求。2深度優(yōu)先搜索法有遞歸和非遞歸兩種設(shè)汁方法一般地，當(dāng)搜索深度較小、問題遞歸形式較明顯時，用遞歸方法設(shè)計較好，它可以使程序結(jié)構(gòu)更簡捷易懂。但當(dāng)搜索深度較大，由于系統(tǒng)堆棧容量的限制，遞歸易產(chǎn)生溢出，用非遞歸設(shè)計方法較合適。3探度優(yōu)先搜索法有廣義和狹義兩種理解。廣義的理解是只要最新產(chǎn)生的結(jié)點(diǎn)(即深度最大的結(jié)點(diǎn))先進(jìn)行擴(kuò)展的搜索法，就稱為深度優(yōu)先搜索。在這種理解情況下，深度優(yōu)先搜索算法有全部保留和不全部保留產(chǎn)生的結(jié)點(diǎn)兩種情況，而狹義的理解是，僅僅指保留全部產(chǎn)生的結(jié)點(diǎn)的算法。本書取前一種廣義的理解。不保留全部結(jié)點(diǎn)的算法，屬于一般的回溯算法范疇。保留全部結(jié)點(diǎn)的算法，實(shí)