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

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

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

3、en 打印一個解 else try(i+1);刪去第i個數字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é)點mr符合條件 then 產生新節(jié)點并存于dep指向的棧頂； if 子節(jié)點是目標 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.上述程序運行產生結點的過程如下圖所示： 結點旁的編號是結點產生的先后順序。從產生的順序可以看出，深度越大的結點越先進行擴展，即先產生它的子結點。例如，有了結點（3）和（31）后，并不是繼續(xù)產生（3）的子結點，而是先產生（31）的子結點（312）。這是由于（31）的深度是2，（3）的深度是1，（31）的深度大，所以先

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

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

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

15、);const n=擴展節(jié)點估計數；waymax=擴展節(jié)點途徑數；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 是目標節(jié)點 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 子結點mr符號條件 then 產生的子結點mr壓入棧； if 子結點mr是目標結點 THEN 輸出 ELSE DFS_TRY（I+1）；棧頂元素出棧（刪去mr）;ENDIF；ENDDO；主程序為：PROGRAM 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產生子結點MR并將其記錄；IF 子結點是目標 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)先搜索基本算法是一樣的，但在具體處理方法上，編程的技巧上，不盡相同，甚至會有很大差別。比如例1的解法還可以這樣來設計：從表中看出，趙同學只喜愛D一本書，無其他選擇余地。因此可以在搜索前就確定下來。為了編程方便，把趙錢二人位置互換，這樣程序只需對張王劉錢四人進行搜索。另外，發(fā)現(xiàn)表

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