深度優(yōu)先搜索算法.doc

深度優(yōu)先搜索算法教程例1 有A、B、C、D、E五本書，要分給張、王、劉、趙、錢五位同學(xué)，每人只能選一本。事先讓每個(gè)人將自己喜愛(ài)的書填寫在下表中。希望你設(shè)計(jì)一個(gè)程序，打印分書的所有可能方案，當(dāng)然是讓每個(gè)人都滿意。（如下圖所示）分析 這個(gè)問(wèn)題中喜愛(ài)的書是隨機(jī)的，沒(méi)有什么規(guī)律，所以用窮舉法比較合適。為編程方便，用1、2、3、4、5分別表示這五本書。這五本書的一種全排列就是五本書的一種分法。例如54321表示第5本書（即E）分給張，第4本書（即D分給王，）第1本書（即A分給錢）?！跋矏?ài)書表”可以用二維數(shù)組來(lái)表示，1表示喜愛(ài)，0表示不喜愛(ài)。算法設(shè)計(jì)：1、 產(chǎn)生5個(gè)數(shù)字的一個(gè)全排列；2、 檢查是否符合“喜愛(ài)書表”的條件，如果符合就打印出來(lái)。3、 檢查是否所有排列都產(chǎn)生了，如果沒(méi)有產(chǎn)生完，則返回1。4、 結(jié)束。算法改進(jìn)：因?yàn)閺堉幌矚g第3、4本書，這就是說(shuō)，1* * * *一類的分法都不符合條件。所以改進(jìn)后的算法應(yīng)當(dāng)是：在產(chǎn)生排列時(shí)，每增加一個(gè)數(shù)，就檢查該數(shù)是否符合條件，不符合，就立即換一個(gè)，符合條件后，再產(chǎn)生下一個(gè)數(shù)。因?yàn)閺牡趇本書到第i+1本書的尋找過(guò)程是相同的，所以可以用遞歸算法。算法如下：procedure try(i); 給第I個(gè)同學(xué)發(fā)書begin for j:=1 to 5 dobeginif 第i個(gè)同學(xué)分給第j本書符合條件 then begin記錄第i個(gè)數(shù); 即j值if i=5 then 打印一個(gè)解 else try(i+1);刪去第i個(gè)數(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.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語(yǔ)言代碼：#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;其中回溯過(guò)程如下：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.上述程序運(yùn)行產(chǎn)生結(jié)點(diǎn)的過(guò)程如下圖所示：結(jié)點(diǎn)旁的編號(hào)是結(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）的深度大，所以先擴(kuò)展。同前邊圖的深度優(yōu)先遍歷聯(lián)系起來(lái)這種在搜索過(guò)程中，深度大的節(jié)點(diǎn)先進(jìn)行擴(kuò)展的算法，稱之為深度優(yōu)先搜索法。簡(jiǎn)稱DFS法。（Depth_First_Search）。深度優(yōu)先搜索的特點(diǎn)：(1) 對(duì)已產(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)入棧，并初始化指針1object, 1top。（注釋：state(x)表示節(jié)點(diǎn)x的狀態(tài)，state(1)表示初始狀態(tài)，object表示作擴(kuò)展的節(jié)點(diǎn)。Top表示由節(jié)點(diǎn)object擴(kuò)展的子節(jié)點(diǎn)。）2、分別用waymax種途徑擴(kuò)展object的子節(jié)點(diǎn)。 (1)從途徑1開(kāi)始擴(kuò)展新節(jié)點(diǎn) 1waynum。（注釋：waymax表示所有可能擴(kuò)展子節(jié)點(diǎn)的途徑的總數(shù)目，waynum表示所選途徑編號(hào)） （2）判斷waynum途徑可行嗎？（即可否擴(kuò)展新節(jié)點(diǎn)）若不行，轉(zhuǎn)2（5）。 （3）對(duì)新節(jié)點(diǎn)設(shè)父指針，新?tīng)顟B(tài)入棧。top+1top，objectfather(top)，state(object)經(jīng)途徑waynum改變后的新?tīng)顟B(tài)state(top)中。(注釋：father(x)節(jié)點(diǎn)x 的父節(jié)點(diǎn)的標(biāo)號(hào)。) （4）top是目標(biāo)節(jié)點(diǎn)嗎？是，則調(diào)用打印結(jié)果子程序print打印結(jié)果路徑。若只要求一個(gè)方案則結(jié)束，否則，讓節(jié)點(diǎn)top出棧再繼續(xù)執(zhí)行下一步。 （5）選擇下一條路徑，即waynum+1waynum，若waynum=waymax，則轉(zhuǎn)2(2)。3、選擇用來(lái)擴(kuò)展的新節(jié)點(diǎn)。 （1）若objecttop，若top=0（?？談t結(jié)束），若top已擴(kuò)展，再轉(zhuǎn)3(2)。 （3）topobject，若object已規(guī)定深度，則轉(zhuǎn)3(2)。否則轉(zhuǎn)2(1)。深度優(yōu)先搜索Pascal語(yǔ)言程序：program dfs(input,output);const n=擴(kuò)展節(jié)點(diǎn)估計(jì)數(shù)；waymax=擴(kuò)展節(jié)點(diǎn)途徑數(shù)；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:=新?tīng)顟B(tài)； if top 是目標(biāo)節(jié)點(diǎn) 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.深度優(yōu)先搜索的基本算法如下：一、遞歸算法遞歸過(guò)程為：procedure DFS_TRY(i);for r:=1 to maxr do if 子結(jié)點(diǎn)mr符號(hào)條件 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：=TRUE；ELSE IF J=MAXJ THEN回溯 ELSE P：=FALSE；ENDIF；UNTIL P=TRUE；UNTIL DEP=0；其中回溯過(guò)程如下：PROCEDURE BACKTRACKING；DEP：=DEP-1；IF DEP0 THEN 取回棧頂元素 ELSE P：=TRUE；不同問(wèn)題的深度優(yōu)先搜索基本算法是一樣的，但在具體處理方法上，編程的技巧上，不盡相同，甚至?xí)泻艽蟛顒e。比如例1的解法還可以這樣來(lái)設(shè)計(jì)：從表中看出，趙同學(xué)只喜愛(ài)D一本書，無(wú)其他選擇余地。因此可以在搜索前就確定下來(lái)。為了編程方便，把趙錢二人位置互換，這樣程序只需對(duì)張王劉錢四人進(jìn)行搜索。另外，發(fā)現(xiàn)表示“喜愛(ài)書表”的數(shù)組有多個(gè)0，為減少不必要的試探，我們改用鏈表來(lái)表示。例如第3位同學(xué)的鏈表是：LIKE（3，0）=2，表示他喜愛(ài)的第一本書編號(hào)是3，最后LIKE（3，3）=0，表示3是最后一本喜愛(ài)的書。深度優(yōu)先搜索算法小結(jié) 1可以用深度優(yōu)先搜索法處理的問(wèn)題是各種各樣的。有的搜索深度是已知和固定的，有的是未知的，有的搜索深度是有限制的，但達(dá)到目標(biāo)的深度不定，但我們也看到，無(wú)論問(wèn)題的內(nèi)容、性質(zhì)、求解要求如何不同，但它們的程序結(jié)構(gòu)都是相同的，即都是第四節(jié)中描述的算法結(jié)構(gòu)，不相同的僅僅是存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)庫(kù)結(jié)構(gòu)、產(chǎn)生規(guī)則和輸出要求。2深度優(yōu)先搜索法有遞歸和非遞歸兩種設(shè)汁方法一般地，當(dāng)搜索深度較小、問(wèn)題遞歸形式較明顯時(shí)，用遞歸方法設(shè)計(jì)較好，它可以使程序結(jié)構(gòu)更簡(jiǎn)捷易懂。但當(dāng)搜索深度較大，由于系統(tǒng)堆棧容量的限制，遞歸易產(chǎn)生溢出，用非遞歸設(shè)計(jì)方法較合適。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í)際上是在數(shù)據(jù)庫(kù)中產(chǎn)生結(jié)點(diǎn)之間的搜索樹(shù)，因此也屬于圖搜索算法的范疇。4不全部保留結(jié)點(diǎn)的深度優(yōu)先搜索法，由于把擴(kuò)展完的結(jié)點(diǎn)從數(shù)據(jù)庫(kù)中彈出刪去，這樣，一般在數(shù)據(jù)庫(kù)中存儲(chǔ)的結(jié)點(diǎn)數(shù)就是深度值，因此它占用的空間較少。所以，當(dāng)搜索樹(shù)的結(jié)點(diǎn)較多，用其他方法易產(chǎn)生內(nèi)存溢出時(shí)，深度優(yōu)先搜索不失為一種有效的求解方法。5從城市路徑的輸出結(jié)果可看出，深度優(yōu)先搜索法找到的第一個(gè)解，不一定是最優(yōu)解。例如城市路徑的最優(yōu)解應(yīng)是COST=13，但第一個(gè)解卻是COST17。如果要求出最優(yōu)解，一種辦法是用第九章將要介紹的動(dòng)態(tài)規(guī)劃法，另一種辦法是修改原算法：把原輸出過(guò)程的地方改為記錄過(guò)程，即記錄達(dá)到當(dāng)前目標(biāo)的路徑和相應(yīng)的路程值，并與前面巳記錄的值加以比較，保留其中最優(yōu)解。等全部搜索完成后，再把保留的最優(yōu)解輸出。練習(xí)題：1、八皇后問(wèn)題：