廣度優(yōu)先搜索

1、一)深度優(yōu)先搜索遍歷算法深度優(yōu)先搜索的過程深度優(yōu)先搜索所遵循的搜索策略是盡可能 “深 ”地搜索圖。 在深度優(yōu)先搜索中， 對于最新 發(fā)現(xiàn)的節(jié)點(diǎn)， 如果它還有以此為起點(diǎn)而未搜索的邊， 就沿此邊繼續(xù)搜索下去。 當(dāng)節(jié)點(diǎn) v 的所 有邊都己被探尋過， 搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn) v 有那條邊的始節(jié)點(diǎn)。 這一過程一直進(jìn)行到已發(fā) 現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。 如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)， 則選擇其中一個作為源節(jié)點(diǎn) 并重復(fù)以上過程，整個進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被發(fā)現(xiàn)為止。即1以給定的某個頂點(diǎn) V0為起始點(diǎn)，訪問該頂點(diǎn)；2選取一個與頂點(diǎn) V0相鄰接且未被訪問過的頂點(diǎn)V1，用V1作為新的起始點(diǎn)，重復(fù)上述過程；3當(dāng)?shù)竭_(dá)

2、一個其所有鄰接的頂點(diǎn)都已被訪問過的頂點(diǎn)Vi時，就退回到新近被訪問過的頂點(diǎn) Vi- 1，繼續(xù)訪問 Vi-1 尚未訪問的鄰接點(diǎn)，重復(fù)上述搜索過程；4直到從任意一個已訪問過的頂點(diǎn)出發(fā)，再也找不到未被訪問過的頂點(diǎn)為止，遍歷便告完成。這種搜索的次序體現(xiàn)了向縱深發(fā)展的趨勢，所以稱之為深度優(yōu)先搜索。深度優(yōu)先搜索算法描述：程序?qū)崿F(xiàn)有兩種方式 - 遞歸與非遞歸。一、遞歸遞歸過程為：Procedure DEF-GO(step)for i:=1 to max doif 子結(jié)點(diǎn)符合條件 then 產(chǎn)生新的子結(jié)點(diǎn)入棧；if 子結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn) then 輸出 else DEF-GO(step+1) ； 棧頂結(jié)點(diǎn)出棧；en

3、dif ；enddo；主程序為：Program DFS ；初始狀態(tài)入棧；DEF-GO(1)；二、非遞歸Program DEF(step) ； step:=0 ； repeat step:=step+1 ； j:=0 ； p:=falserepeatj:=j+1 ；if 結(jié)點(diǎn)符合條件 then產(chǎn)生子結(jié)點(diǎn)入棧； if 子結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn) then 輸出 else p:=true ； elseif j>=max then 回溯 p:=false ； endif ；until p=true ； until step=0 ； 回溯過程如下： Procedure BACK ；棧頂結(jié)點(diǎn)出棧step:=s

4、tep-1 if step>0 then else p:=true例如 八數(shù)碼難題 -已知8個數(shù)的起始狀態(tài)如圖86(a)(a),要得到目標(biāo)狀態(tài)為圖 1(34b)。6b)1的其中，并按照結(jié)點(diǎn)擴(kuò)展的順序加以編號。 粗線條路徑表示求得的一個解。 從圖中可見， 深度優(yōu)先搜索過程是 直到深度界限為止， 回溯一步， 再繼續(xù)往下搜索， 直到找到目標(biāo)狀圖1求解時 , 首先要生成一棵結(jié)點(diǎn)的搜索樹,按照深度優(yōu)先搜索算法,我們可以生成圖 搜索樹。 圖中,所有結(jié)點(diǎn)都用相應(yīng)的數(shù)據(jù)庫來標(biāo)記, 我們設(shè)置深度界限為5。 沿著一條路徑進(jìn)行下去, 態(tài)或OPEN表為空為止。3S1144311)313114inTtT«

5、;JT5ii«II1«4MTIts114If I!« 4,i11)ITSEli3 F417S6313iti313StA175 !3M4Ta、 43iti 7H tti3$ I * rsiSS圖1iti(41L7S113It*TriSHi67<Lif.3-，芳IP程序:program No8_DFS;八數(shù)碼的深度優(yōu)先搜索算法 Co nstDir : array1.4,1.2of in teger = (1,0),(-1,0),(0,1),(0,-1); maxN = 15;TypeT8No = array1.3,1.3of in teger;tList = r

6、ecordstate : T8No; x0,y0 : in teger;en d;Var可以承受的最大深度Source,Target : T8No;List,Save : array0.maxNof tList;Open ,Best : in teger;綜合數(shù)據(jù)庫，最優(yōu)解路徑pro cedure GetI nfo;Fun ction Same(A,B : T8No):Boolea n;function Not_A pp ear(New : tList):boolea n;見程序見程序見程序111pro cedure Move(N : tList;d : in teger;var ok : b

7、oolea n; var New : tList); 見程序1第3頁共17頁輸出procedure GetOutInfo; var i,x,y : integer; begin writeln('total = ',best); for i:=1 to best+1 do begin for x:=1 to 3 do begin for y:=1 to 3 do write(Savei.Statex,y,' '); writeln;end;writeln;end;end;Procedure Recursive;Var i : integer;New: tList

8、;ok : boolean;BeginIf Open-1>=Best then exit;If Same(ListOpen.state,Target) then begin Best:=Open-1;Save:=List;end;For i:=1 to 4 do beginMove(ListOpen,i,OK,New);if ok and not_Appear(New) then begin inc(open);ListOpen:=New;Recursive;dec(Open);End;End;End;遞歸搜索過程如果找到解，保存當(dāng)前最優(yōu)解依次選用規(guī)則如果沒有重復(fù)插入綜合數(shù)據(jù)庫 繼續(xù)搜索

9、 退棧 搜索主過程 初始化 procedure Main; var x,y : integer; beginList1.state:=Source;for x:=1 to 3 dofor y:=1 to 3 do if Sourcex,y=0 then begin List1.x0:=x; List1.y0:=y;end;Best:=MaxN;Open:=1;Recursive;If Best=maxint then writeln('No answer')Else GetOutInfo;end; 開始搜索 BeginAssign(Input,'input.txt

10、9;);ReSet(Input);Assign(Output,'Output.txt');ReWrite(Output);GetInfo;Main;Close(Input);Close(Output);End.面的八數(shù)碼程序利用到了遞歸來實(shí)現(xiàn)，其實(shí)深度優(yōu)先搜索還有一種無需遞歸的實(shí)現(xiàn)方式， 面我們介紹一下深度優(yōu)先的一般實(shí)現(xiàn)方法：遞歸算法和非遞歸算法。遞歸算法偽代碼：procedure DFS_ recursive(N);1.2.3.4.5.6.7.8.9.if N=target then 更新當(dāng)前最優(yōu)值并保存路徑 for r:=1 to 規(guī)則數(shù) do New:=Expand(N,

11、r)if 值節(jié)點(diǎn) New 符合條件 then 產(chǎn)生的子節(jié)點(diǎn) New 壓入棧 ; DFS_recursive(i+1); 棧頂元素出棧 ;program DFS;1. 初始化 ;2. DFS_recursive(N);非遞歸算法偽代碼：procedure Backtracking;1.2. if dep>0 then 取出棧頂元素3.dep:=dep-1;else p:=true;program DFS; dep:=0; Repeat dep:=dep+1; j:=0;brk:=false; Repeat1.2.3.4.5.第 7 頁 共 17 頁6.7.8.9.10.11.12.13.1

12、4.15.16.j:=j+1; New=Expand(Trackdep,j); if New 符合條件 then 產(chǎn)生子節(jié)點(diǎn) New 并將其壓棧 ;else if j>= 規(guī)則數(shù)If 子節(jié)點(diǎn) New=target then 更新最優(yōu)值并出棧 else brk:=true;then Backtracking else brk:=false;Until brk=trueUntil dep=0;兩種方式本質(zhì)上是等價，但兩者也時有區(qū)別的。1 遞歸方式實(shí)現(xiàn)簡單，非遞歸方式較之比較復(fù)雜；遞歸方式需要利用?？臻g， 如果搜索量過大的話， 可能造成棧溢出， 所以在?？臻g無法滿足 的情況下，選用非遞歸實(shí)現(xiàn)方

13、式較好。二）廣度優(yōu)先搜索遍歷算法一寬度優(yōu)先搜索的過程 寬度優(yōu)先搜索算法（又稱寬度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是 很多重要的圖的算法的原型。 Dijkstra 單源最短路徑算法和 Prim 最小生成樹算法都采用了 和寬度優(yōu)先搜索類似的思想。寬度優(yōu)先算法的核心思想是：從初始節(jié)點(diǎn)開始，應(yīng)用算符生成第一層節(jié)點(diǎn)，檢查目標(biāo)節(jié) 點(diǎn)是否在這些后繼節(jié)點(diǎn)中， 若沒有， 再用產(chǎn)生式規(guī)則將所有第一層的節(jié)點(diǎn)逐一擴(kuò)展， 得到第 二層節(jié)點(diǎn)， 并逐一檢查第二層節(jié)點(diǎn)中是否包含目標(biāo)節(jié)點(diǎn)。 若沒有， 再用算符逐一擴(kuò)展第二層 的所有節(jié)點(diǎn) , ，如此依次擴(kuò)展，檢查下去，直到發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)為止。即1從圖中的某一頂點(diǎn) V

14、0開始，先訪問V0;2訪問所有與 V0相鄰接的頂點(diǎn) V1, V2,Vt;3依次訪問與 VI，V2,，Vt相鄰接的所有未曾訪問過的頂點(diǎn)；4循此以往，直至所有的頂點(diǎn)都被訪問過為止。 這種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)長的趨勢，所以稱之為廣度優(yōu)先搜索。二、廣度優(yōu)先搜索算法描述：Program Bfs ;初始化，初始狀態(tài)存入 0P EN表;隊列首指針 head:=0; 尾指針 tail:=1 ;repeat指針 head 后移一位，指向待擴(kuò)展結(jié)點(diǎn);for I=1 to max do max為產(chǎn)生子結(jié)點(diǎn)的規(guī)則數(shù) beginif子結(jié)點(diǎn)符合條件thenbegintailif指針增1，把新結(jié)點(diǎn)存入列尾；新結(jié)點(diǎn)與

15、原已產(chǎn)生結(jié)點(diǎn)重復(fù)then刪去該結(jié)點(diǎn)（取消入隊，tail減1）elseif新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)then輸出并退出;end; end;隊列空until(tail>=head); 三、廣度優(yōu)先搜索注意事項：1、每生成一個子結(jié)點(diǎn)，就要提供指向它們父親結(jié)點(diǎn)的指針。當(dāng)解出現(xiàn)時候，通過逆向 跟蹤，找到從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑。2、生成的結(jié)點(diǎn)要與前面所有已經(jīng)產(chǎn)生結(jié)點(diǎn)比較，以免出現(xiàn)重復(fù)結(jié)點(diǎn)，浪費(fèi)時間，還有 可能陷入死循環(huán)。3、 如果目標(biāo)結(jié)點(diǎn)的深度與“費(fèi)用”（如：路徑長度）成正比，那么，找到的第一個解 即為最優(yōu)解，這時，搜索速度比深度搜索要快些；如果結(jié)點(diǎn)的“費(fèi)用”不與深度成正比時， 第一次找到的解不一定是最

16、優(yōu)解。4、廣度優(yōu)先搜索的效率還有賴于目標(biāo)結(jié)點(diǎn)所在位置情況，如果目標(biāo)結(jié)點(diǎn)深度處于較深 層時，需搜索的結(jié)點(diǎn)數(shù)基本上以指數(shù)增長。F面我們看看怎樣用寬度優(yōu)先搜索來解決八數(shù)碼問題。搜索樹上的所有結(jié)點(diǎn)都 粗線條路徑表明求得的例如圖2給出廣度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時所生成的搜索樹。 標(biāo)記它們所對應(yīng)的狀態(tài)，每個結(jié)點(diǎn)旁邊的數(shù)字表示結(jié)點(diǎn)擴(kuò)展的順序。 一個解。從圖中可以看出，擴(kuò)展2 6個結(jié)點(diǎn)和生成4 6個結(jié)點(diǎn)之后，才求得這個解。此外, 直接觀察此圖表明，不存在有更短走步序列的解。3647113£113IM175113Tft114|4|MlTSd1H3ih加 L靈iSi1_in2«<ITS

17、環(huán)J75l£32L4T磚TH出312£1333K2Q創(chuàng)1艄NS止8w7A5761Ki191(U-33lE3M才門 3SI2laM3Li1417«57W714THT>+71*TH荷TJ4口1U331innlto113昭914MlMStJ4m3147H測71+i?iiJiITJ|ILSL5lTiSfinW1砧173Sl21L4如如37144IS213&昭L7SIls圖2廣度優(yōu)先搜索圖第7頁共17頁程序?qū)崿F(xiàn)算法：Program BFS ；建立數(shù)據(jù)庫 data ；數(shù)據(jù)庫賦初值；設(shè)隊列頭指針 H:=0 ；隊列尾指針 L:=1 ； repeat取下一個H所指的結(jié)

18、點(diǎn)；for i:=1 to max do i為產(chǎn)生新結(jié)點(diǎn)規(guī)則編號 beginL增1，把新結(jié)點(diǎn)存入數(shù)據(jù)庫隊尾；記錄父結(jié)點(diǎn)的位置;if 新結(jié)點(diǎn)與原有結(jié)點(diǎn)重復(fù) then刪去該結(jié)點(diǎn) （L 減 1）elseif 新結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn) then 輸出并退出；end；end；until H>=L 隊列為空 程序：program 8no_bfs; 八數(shù)碼的寬度優(yōu)先搜索算法 Const 四種移動方向，對應(yīng)產(chǎn)生式規(guī)則 父指針 深度 0 的位置 棋盤狀態(tài) Dir : array1.4,1.2of integer = (1,0),(-1,0),(0,1),(0,-1);N=10000;TypeT8No = arra

19、y1.3,1.3of integer;TList = recordFather : integer; dep : byte;X0,Y0 : byte; State : T8No;end;VarSource,Target : T8No; List : array0.10000 of TList; Closed,Open,Best : integer Answer : integer;Found : Boolean; 綜合數(shù)據(jù)庫 Best 表示最優(yōu)移動次數(shù) 記錄解 解標(biāo)志 讀入初始和目標(biāo)節(jié)點(diǎn) procedure GetInfo; var i,j : integer;beginfor i:=1 to

20、 3 dofor j:=1 to 3 do read(Sourcei,j);for i:=1 to 3 dofor j:=1 to 3 do read(Targeti,j); end; 初始化 procedure Initialize; var x,y : integer; beginFound:=false;Closed:=0;Open:=1; with List1 do beginState:=Source;dep:=0;Father:=0;For x:=1 to 3 doFor y:=1 to 3 doif Statex,y=0 then Begin x0:=x;y0:=y; End;

21、end;end; 判斷 A,B 狀態(tài)是否相等 Function Same(A,B : T8No):Boolean; Var i,j : integer;Begin Same:=false;For i:=1 to 3 do for j:=1 to 3 do if Ai,j<>Bi,j then exit; Same:=true;End; 判斷 New 是否在 List 中出現(xiàn) function Not_Appear(New : tList):boolean; var i : integer; beginNot_Appear:=false;for i:=1 to Open do if

22、Same(New.State,Listi.State) then exit; Not_Appear:=true;end;procedure Move(N : tList;d : integer;var ok : boolean;var New : tList); 將第 d 條規(guī)則作用于 N 得到 New,OK 是 New 是否可行的標(biāo)志 var x,y : integer;beginX := N.x0 + Dird,1;Y := N.y0 + Dird,2; 判斷 New 的可行性 If not (X > 0) and ( X < 4 ) and ( Y > 0 ) and

23、( Y < 4 ) then begin ok:=false;exit end;OK:=true;New.State:=N.State; New=Expand(N,d)New.StateX,Y:=0;New.StateN.x0,N.y0:=N.StateX,Y;New.X0:=X;New.Y0:=Y;end;procedure Add(new : tList); beginIf not_Appear(New) then BeginInc(Open);ListOpen := New;end;end; 插入節(jié)點(diǎn) New 如果 New 沒有在 List 出現(xiàn) New 加入 Open 表proc

24、edure Expand(Index : integer; var N : tList); var i : integer;New : tList;OK : boolean;BeginIf Same(N.State , Target) then beginFound := true;Best :=N.Dep;Answer:=Index;Exit;end;For i := 1 to 4 do begin Move(N,i,OK,New); if not ok then continue; New.Father := Index;New.Dep :=N.dep + 1; Add(New);end;

25、end; 擴(kuò)展 N 的子節(jié)點(diǎn) 如果找到解 依次使用4條規(guī)則第 17 頁 共 17 頁輸出 遞歸輸出每一個解procedure GetOutInfo;procedure Outlook(Index : integer); var i,j : integer;beginif Index=0 then exit; Outlook(ListIndex.Father); with ListIndex do for i:=1 to 3 do beginfor j:=1 to 3 do write(Statei,j,' ');writeln;end;writeln;end;beginWrit

26、eln('Total = ',Best);Outlook(Answer);end;procedure Main;beginRepeatInc(Closed);Expand(Closed,ListClosed);Until (Closed>=Open) or Found; If Found then GetOutInfo 搜索主過程 擴(kuò)展 Closedelse Writeln('No answer'); 存在解 無解 end;BeginAssign(Input,'input.txt');ReSet(Input);Assign(Output,&

27、#39;Output.txt');ReWrite(Output);GetInfo;Initialize;Main;Close(Input);Close(Output);End.例 1 在一個瓶中裝有 80 毫升化學(xué)溶劑，實(shí)驗中需要精確地平分成兩份，沒有量具，只 有兩個杯子， 其中一個杯子的容量是 50 毫升，另一個是 30 毫升，試設(shè)計一個程序?qū)⒒瘜W(xué)溶 劑對分成兩個 40 毫升，并以最少步驟給出答案。分析:三個杯子水的初始狀態(tài)為：8 0、0、0,生成新結(jié)點(diǎn)狀態(tài)的方法為：將一個不空 的杯子水倒入一個不滿的杯中，且結(jié)點(diǎn)狀態(tài)不重復(fù)，直到生成目標(biāo)結(jié)點(diǎn)為止。算法步驟 :1. 數(shù)據(jù)庫：用數(shù)組d構(gòu)成

28、存放生成結(jié)點(diǎn)(杯子水狀態(tài))的隊；數(shù)組P作為指向父結(jié)點(diǎn)的指 針； t 和 s 作為隊頭與隊尾指針。2結(jié)點(diǎn)的產(chǎn)生：以避免死循環(huán)； 輸出。(1) 將結(jié)點(diǎn)中不空的杯子水倒入一個不滿的杯子中，生成新的結(jié)點(diǎn)并記下父結(jié)點(diǎn)位置；(2) 判斷新結(jié)點(diǎn)是否已生成過，(3) 生成的結(jié)點(diǎn)若為目標(biāo)結(jié)點(diǎn)， 3搜索策略：廣度優(yōu)先搜索。源程序如下 :program ex3;typestatus= array 1.3 of integer;constv: array 1.3 of integer =(80 var，50,30);d: array 1.200 of status; p: array 1.200 of integer

29、;t,s,i,j: integer; procedure draw(f: integer); varm: array 1.20 of integer;i,j,k: integer; beginj:=0;while f<>1 do begin inc(j); mj:=f; f:=pf;end; writeln;writeln('Start: ',d1,1:3,d1,2:3,d1,3:3);for i:=j downto 1 do begin write('Step No.',j+1-i,': '); for k:=1 to 3 do w

30、rite(dmi,k:3); writeln;end; writeln('End.');halt; end; function exampass(w: integer): boolean; vari: integer;beginfor i:=1 to w-1 do if (di,1=dw,1) and (di,2=dw,2) and (di,3=dw,3) then beginexampass:=false; exit; end;exampass:=true;end;function isobject(w: integer): boolean; begin輸出 新結(jié)點(diǎn)是否以前生

31、成過 是否為目標(biāo)結(jié)點(diǎn) if (dw,1=40) and (dw,2=40) then isobject:=trueelse isobject:=false;end;begin 生成新結(jié)點(diǎn) ,將一個不空的杯子水倒入一個不滿的杯子中d1,1:=80; d1,2:=0; d1,3:=0;p1:=0;t:=1; s:=2;repeatfor i:=1 to 3 doif dt,i<>0 thenfor j:=1 to 3 doif (i<>j) and (dt,j<>vj) then beginds:=dt;ds,j:=ds,j+ds,i;ds,i:=0;if ds

32、,j>vj then beginds,i:=ds,j-vj;ds,j:=vj;end;ps:=t;if exampass(s) then beginif isobject(s) then draw(s);inc(s);end;end;inc(t);until t>=s;writeln('NoWay');end."1-7"例 2 跳棋的原始狀態(tài)如下圖。其中 "0" 表示空格， "-" 表示白子， "+" 表示黑子， 表示棋盤格編號。跳棋的規(guī)則是：1任意一個棋子可移到相鄰的空位上；2可跳過一

33、個或兩個棋子到空位上，與跳過的棋子的顏色無關(guān)；3.棋子向左向右跳不限。例如：4到1、5到 4、3到 5、6到3是成功的四步走法。請編一程序，用 10步完成從 原始狀態(tài)跳變成目標(biāo)狀態(tài)。要求打印跳每一步后的狀態(tài)。用數(shù)字表示棋盤格子的代號。1 2 3 4 5 6 7 原始位置 0 - - - + + + 目標(biāo)位置 + + + - - - 0分析 : 此題可以用廣度與深度搜索兩種方法求解，通過運(yùn)行兩種解法的程序，我們可以 粗略地知道兩種算法的區(qū)別。算法步驟 :1數(shù)據(jù)庫：數(shù)組g構(gòu)成隊，存放棋子的狀態(tài)；數(shù)組P作為指針指向其父結(jié)點(diǎn)位置; S分別表示隊頭與隊尾指針。2結(jié)點(diǎn)的產(chǎn)生：與位置間距 -3到3的棋子可移

34、入空位，生成新結(jié)點(diǎn)狀態(tài)。3搜索策略：廣度優(yōu)先搜索。源程序如下 :program ex143-1; 廣度優(yōu)先搜索 uses time;typestatus=string7;conststart: status ='0-+'obj: status ='+-0'var a,b,c: timetype; g: array 1.200 of status; p: array 1.200 of integer; i,j,k: integer; t,s: integer;輸出 procedure draw(f: integer); varm: array 1.10 of in

35、teger;i,j: integer;begin j:=0; while f<>1 do begin inc(j); mj:=f; f:=pf;end; writeln; writeln('Start: ',start);for i:=j downto 1 do writeln('Step No.',j+1-i,': ',gmi); writeln('End'); gettimenow(b); howlong(a,b,c);printtime('Time Take: ',c); halt;end;判斷結(jié)

36、點(diǎn)有否重復(fù) function exampass(w: integer): boolean; vari: integer;beginfor i:=1 to w-1 do if gi=gw then begin exampass:=false; exit;end; exampass:=true; end; begin 生成新結(jié)點(diǎn) gettimenow(a); g1:=start; p1:=0; t:=1; s:=2; repeat k:=pos('0',gt); for i:=-3 to 3 do if (i<>0) and (k+i>=1) and (k+i<=7) then begin gs:=gt;gs,k:=gs,k+i; gs,k+i:='0' ps:=t;if exampass(s) then begin if gs=obj then draw(s); inc(s);end; end; inc(t); until t>=s; writeln('NoWay');end.算法驟 （ 二）:1. 數(shù)據(jù)庫：數(shù)組g構(gòu)成堆棧，存放棋子的狀態(tài)