深度優先搜索算法教程例1 有A、B、C、D、E五本書，要分給張、王、劉、趙、錢五位同學，每人只能選一本。事先讓每個人將自己喜愛的書填寫在下表中。希望你設計一個程序，打印分書的所有可能方案，當然是讓每個人都滿意。（如下圖所示）分析 這個問題中喜愛的書是隨機的，沒有什么規律，所以用窮舉法比較合適。為編程方便，用1、2、3、4、5分別表示這五本書。這五本書的一種全排列就是五本書的一種分法。例如54321表示第5本書（即E）分給張，第4本書（即D分給王，）第1本書（即A分給錢）。“喜愛書表”可以用二維數組來表示，1表示喜愛，0表示不喜愛。算法設計：1、 產生5個數字的一個全排列；2、 檢查是否符合“喜愛書表”的條件，如果符合就打印出來。3、 檢查是否所有排列都產生了，如果沒有產生完，則返回1。4、 結束。算法改進：因為張只喜歡第3、4本書，這就是說，1* * * *一類的分法都不符合條件。所以改進后的算法應當是：在產生排列時，每增加一個數，就檢查該數是否符合條件，不符合，就立即換一個，符合條件后，再產生下一個數。因為從第i本書到第i+1本書的尋找過程是相同的，所以可以用遞歸算法。算法如下：procedure try(i); 給第I個同學發書begin for j:=1 to 5 dobeginif 第i個同學分給第j本書符合條件 then begin記錄第i個數; 即j值if i=5 then 打印一個解 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.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,j0) then begin flag:=flag+j; booki:=j; 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#includeint 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,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=maxr then 回溯 else p:=flase; endif;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,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; 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,r0)and (r=5 then back else p:=false until p=true; until dep=0; close(f);end.上述程序運行產生結點的過程如下圖所示：結點旁的編號是結點產生的先后順序。從產生的順序可以看出，深度越大的結點越先進行擴展，即先產生它的子結點。例如，有了結點（3）和（31）后，并不是繼續產生（3）的子結點，而是先產生（31）的子結點（312）。這是由于（31）的深度是2，（3）的深度是1，（31）的深度大，所以先擴展。同前邊圖的深度優先遍歷聯系起來這種在搜索過程中，深度大的節點先進行擴展的算法，稱之為深度優先搜索法。簡稱DFS法。（Depth_First_Search）。深度優先搜索的特點：(1) 對已產生的節點按深度排序,深度大的先得到擴展，即先產生它的子節點。(2) 深度大的節點是后產生的，但先得到擴展，即“后產生，先擴展”，因此，采用堆棧作為該算法的數據結構。深度優先搜索的基本思想：1、把初始狀態賦到state(1)中，即初狀態入棧，并初始化指針1object, 1top。（注釋：state(x)表示節點x的狀態，state(1)表示初始狀態，object表示作擴展的節點。Top表示由節點object擴展的子節點。）2、分別用waymax種途徑擴展object的子節點。 (1)從途徑1開始擴展新節點 1waynum。（注釋：waymax表示所有可能擴展子節點的途徑的總數目，waynum表示所選途徑編號） （2）判斷waynum途徑可行嗎？（即可否擴展新節點）若不行，轉2（5）。 （3）對新節點設父指針，新狀態入棧。top+1top，objectfather(top)，state(object)經途徑waynum改變后的新狀態state(top)中。(注釋：father(x)節點x 的父節點的標號。) （4）top是目標節點嗎？是，則調用打印結果子程序print打印結果路徑。若只要求一個方案則結束，否則，讓節點top出棧再繼續執行下一步。 （5）選擇下一條路徑，即waynum+1waynum，若waynum=waymax，則轉2(2)。3、選擇用來擴展的新節點。 （1）若objecttop，若top=0（棧空則結束），若top已擴展，再轉3(2)。 （3）topobject，若object已規定深度，則轉3(2)。否則轉2(1)。深度優先搜索Pascal語言程序：program dfs(input,output);const n=擴展節點估計數；waymax=擴展節點途徑數；var state, father：array1.n of integer;top, object, waynum：integer;procedure print(v：integer);beginwhile v0 dobegin write(statev, 0 dobeginfor waynum:=1 to waymax do （第二步） begin if way(maxnum) 可行 then begin top:=top+1; fathertop:=object; statetop:=新狀態； if top 是目標節點 then begin print(top); top:=top-1; end; end; end; if topobject then object:=top（第三步）else repeat top:=top-1; object:=top until topfathertop+1;end;end.深度優先搜索的基本算法如下：一、遞歸算法遞歸過程為：procedure 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；初始狀態入棧；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：=TRUE；ELSE IF J=MAXJ THEN回溯 ELSE P：=FALSE；ENDIF；UNTIL P=TRUE；UNTIL DEP=0；其中回溯過程如下：PROCEDURE BACKTRACKING；DEP：=DEP-1；IF DEP0 THEN 取回棧頂元素 ELSE P：=TRUE；不同問題的深度優先搜索基本算法是一樣的，但在具體處理方法上，編程的技巧上，不盡相同，甚至會有很大差別。比如例1的解法還可以這樣來設計：從表中看出，趙同學只喜愛D一本書，無其他選擇余地。因此可以在搜索前就確定下來。為了編程方便，把趙錢二人位置互換，這樣程序只需對張王劉錢四人進行搜索。另外，發現表示“喜愛書表”的數組有多個0，為減少不必要的試探，我們改用鏈表來表示。例如第3位同學的鏈表是：LIKE（3，0）=2，表示他喜愛的第一本書編號是3，最后LIKE（3，3）=0，表示3是最后一本喜愛的書。深度優先搜索算法小結 1可以用深度優先搜索法處理的問題是各種各樣的。有的搜索深度是已知和固定的，有的是未知的，有的搜索深度是有限制的，但達到目標的深度不定，但我們也看到，無論問題的內容、性質、求解要求如何不同，但它們的程序結構都是相同的，即都是第四節中描述的算法結構，不相同的僅僅是存儲結點的數據庫結構、產生規則和輸出要求。2深度優先搜索法有遞歸和非遞歸兩種設汁方法一般地，當搜索深度較小、問題遞歸形式較明顯時，用遞歸方法設計較好，它可以使程序結構更簡捷易懂。但當搜索深度較大，由于系統堆棧容量的限制，遞歸易產生溢出，用非遞歸設計方法較合適。3探度優先搜索法有廣義和狹義兩種理解。廣義的理解是只要最新產生的結點(即深度最大的結點)先進行擴展的搜索法，就稱為深度優先搜索。在這種理解情況下，深度優先搜索算法有全部保留和不全部保留產生的結點兩種情況，而狹義的理解是，僅僅指保留全部產生的結點的算法。本書取前一種廣義的理解。不保留全部結點的算法，屬于一般的回溯算法范疇。保留全部結點的算法，實際上是在數據庫中產生結點之間的搜索樹，因此也屬于圖搜索算法的范疇。4不全部保留結點的深度優先搜索法，由于把擴展完的結點從數據庫中彈出刪去，這樣，一般在數據庫中存儲的結點數就是深度值，因此它占用的空間較少。所以，當搜索樹的結點較多，用其他方法易產生內存溢出時，深度優先搜索不失為一種有效的求解方法。5從城市路徑的輸出結果可看出，深度優先搜索法找到的第一個解，不一定是最優解。例如城市路徑的最優解應是COST=13，但第一個解卻是COST17。如果要求出最優解，一種辦法是用第九章將要介紹的動態規劃法，另一種辦法是修改原算法：把原輸出過程的地方改為記錄過程，即記錄達到當前目標的路徑和相應的路程值，并與前面巳記錄的值加以比較，保留其中最優解。等全部搜索完成后，再把保留的最優解輸出。練習題：1、八皇后問題：