廣度優(yōu)先搜索-在線瀏覽
2024-09-03 16:46本頁面
【正文】 {開始搜索} If Best=maxint then writeln(39。) Else GetOutInfo。Begin Assign(Input,39。)。 Assign(Output,39。)。 GetInfo。 Close(Input)。End.上面的八數(shù)碼程序利用到了遞歸來實(shí)現(xiàn)，其實(shí)深度優(yōu)先搜索還有一種無需遞歸的實(shí)現(xiàn)方式，下面我們介紹一下深度優(yōu)先的一般實(shí)現(xiàn)方法：遞歸算法和非遞歸算法。1. if N=target then 更新當(dāng)前最優(yōu)值并保存路徑。6. DFS_recursive(i+1)。8. ]9. ]program DFS。2. DFS_recursive(N)。1. dep:=dep1。program DFS。2. Repeat3. dep:=dep+1。brk:=false。7. New=Expand(Track[dep],j)。10. If 子節(jié)點(diǎn)New=target then 更新最優(yōu)值并出棧11. else brk:=true。15. Until brk=true16. Until dep=0。1． 遞歸方式實(shí)現(xiàn)簡(jiǎn)單，非遞歸方式較之比較復(fù)雜；遞歸方式需要利用棧空間，如果搜索量過大的話，可能造成棧溢出，所以在?？臻g無法滿足的情況下，選用非遞歸實(shí)現(xiàn)方式較好。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。若沒有，再用算符逐一擴(kuò)展第二層的所有節(jié)點(diǎn)……，如此依次擴(kuò)展，檢查下去，直到發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)為止?！ ∵@種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)長(zhǎng)的趨勢(shì)，所以稱之為廣度優(yōu)先搜索。尾指針tail:=1；repeat 指針head后移一位，指向待擴(kuò)展結(jié)點(diǎn)； for I=1 to max do {max為產(chǎn)生子結(jié)點(diǎn)的規(guī)則數(shù)} begin if 子結(jié)點(diǎn)符合條件 then begin tail指針增1，把新結(jié)點(diǎn)存入列尾； if新結(jié)點(diǎn)與原已產(chǎn)生結(jié)點(diǎn)重復(fù)then刪去該結(jié)點(diǎn)（取消入隊(duì)，tail減1） else if新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)then輸出并退出； end。 until(tail=head)。當(dāng)解出現(xiàn)時(shí)候，通過逆向跟蹤，找到從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑。如果目標(biāo)結(jié)點(diǎn)的深度與“費(fèi)用”（如：路徑長(zhǎng)度）成正比，那么，找到的第一個(gè)解即為最優(yōu)解，這時(shí)，搜索速度比深度搜索要快些；如果結(jié)點(diǎn)的“費(fèi)用”不與深度成正比時(shí)，第一次找到的解不一定是最優(yōu)解。下面我們看看怎樣用寬度優(yōu)先搜索來解決八數(shù)碼問題。搜索樹上的所有結(jié)點(diǎn)都標(biāo)記它們所對(duì)應(yīng)的狀態(tài)，每個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示結(jié)點(diǎn)擴(kuò)展的順序。從圖中可以看出，擴(kuò)展２６個(gè)結(jié)點(diǎn)和生成４６個(gè)結(jié)點(diǎn)之后，才求得這個(gè)解?！ D2 廣度優(yōu)先搜索圖 程序?qū)崿F(xiàn)算法： Program BFS； 建立數(shù)據(jù)庫data；數(shù)據(jù)庫賦初值； 設(shè)隊(duì)列頭指針H:=0；隊(duì)列尾指針L:=1； repeat 取下一個(gè)H所指的結(jié)點(diǎn)； for i:=1 to max do {i為產(chǎn)生新結(jié)點(diǎn)規(guī)則編號(hào)} begin L增1，把新結(jié)點(diǎn)存入數(shù)據(jù)庫隊(duì)尾；記錄父結(jié)點(diǎn)的位置； if 新結(jié)點(diǎn)與原有結(jié)點(diǎn)重復(fù) then 刪去該結(jié)點(diǎn)(L減1) else if 新結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn) then 輸出并退出； end； end； until H=L {隊(duì)列為空}程序：program 8no_bfs。 N=10000。 TList = record Father : integer。 {深度} X0,Y0 : byte。 {棋盤狀態(tài) } end。 List : array[0..10000] of TList。 {記錄解} Found : Boolean。 {讀入初始和目標(biāo)節(jié)點(diǎn)} var i,j : integer。 for i:=1 to 3 do for j:=1 to 3 do read(Target[i,j])。 procedure Initialize。 begin Found:=false。Open:=1。dep:=0。 For x:=1 to 3 do For y:=1 to 3 do if State[x,y]=0 then Begin x0:=x。 End。 end。 {判斷A,B狀態(tài)是否相等 } Var i,j : integer。 For i:=1 to 3 do for j:=1 to 3 do if A[i,j]B[i,j] then exit。 End。 {判斷New是否在List中出現(xiàn) } var i : integer。 for i:=1 to Open do if Same(,List[i].State) then exit。 end。d : integer。var New : tList)。 begin X := + Dir[d,1]。 {判斷New的可行性} If not ((X 0) and ( X 4 ) and ( Y 0 ) and ( Y 4 )) then begin ok:=false。 OK:=true。 {New=Expand(N,d)} [X,Y]:=0。 :=X。 end。 {插入節(jié)點(diǎn)New} begin If not_Appear(New) then Begin {如果New沒有在List出現(xiàn) } Inc(Open)。 end。 procedure Expand(Index : integer。 {擴(kuò)展N的子節(jié)點(diǎn)} var i : integer。 OK : boolean。 Best :=。 Exit。 For i := 1 to 4 do begin
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1