廣度優(yōu)先搜索-文庫吧資料
2024-08-06 16:46本頁面
【正文】 Outlook(List[Index].Father)。 {遞歸輸出每一個解} var i,j : integer。 procedure GetOutInfo。 end。 := + 1。 if not ok then continue。 end。 Answer:=Index。 Begin If Same( , Target) then begin {如果找到解} Found := true。 New : tList。 var N : tList)。 end。 {New加入Open表 } List[Open] := New。 procedure Add(new : tList)。:=Y。 [,]:=[X,Y]。:=。exit end。 Y := + Dir[d,2]。 {將第d條規(guī)則作用于N得到New,OK是New是否可行的標(biāo)志 } var x,y : integer。var ok : boolean。 procedure Move(N : tList。 Not_Appear:=true。 begin Not_Appear:=false。 function Not_Appear(New : tList):boolean。 Same:=true。 Begin Same:=false。 Function Same(A,B : T8No):Boolean。 end。y0:=y。Father:=0。 with List[1] do begin State:=Source。 Closed:=0。 {初始化} var x,y : integer。 end。 begin for i:=1 to 3 do for j:=1 to 3 do read(Source[i,j])。 {解標(biāo)志} procedure GetInfo。 {綜合數(shù)據(jù)庫 } Closed,Open,Best : integer { Best表示最優(yōu)移動次數(shù)} Answer : integer。Var Source,Target : T8No。 {0的位置} State : T8No。 {父指針} dep : byte。Type T8No = array[1..3,1..3]of integer。 {八數(shù)碼的寬度優(yōu)先搜索算法}Const Dir : array[1..4,1..2]of integer {四種移動方向，對應(yīng)產(chǎn)生式規(guī)則} = ((1,0),(1,0),(0,1),(0,1))。此外，直接觀察此圖表明，不存在有更短走步序列的解。粗線條路徑表明求得的一個解。例如 圖2給出廣度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時所生成的搜索樹。廣度優(yōu)先搜索的效率還有賴于目標(biāo)結(jié)點所在位置情況，如果目標(biāo)結(jié)點深度處于較深層時，需搜索的結(jié)點數(shù)基本上以指數(shù)增長。生成的結(jié)點要與前面所有已經(jīng)產(chǎn)生結(jié)點比較，以免出現(xiàn)重復(fù)結(jié)點，浪費時間，還有可能陷入死循環(huán)。 {隊列空}三、廣度優(yōu)先搜索注意事項：每生成一個子結(jié)點，就要提供指向它們父親結(jié)點的指針。end。二、廣度優(yōu)先搜索算法描述：Program Bfs；初始化，初始狀態(tài)存入OPEN表；隊列首指針head:=0。即⒈從圖中的某一頂點V0開始，先訪問V0； ?、苍L問所有與V0相鄰接的頂點V1，V2，......，Vt； ⒊依次訪問與V1，V2，......，Vt相鄰接的所有未曾訪問過的頂點； ?、囱艘酝敝了械捻旤c都被訪問過為止。寬度優(yōu)先算法的核心思想是：從初始節(jié)點開始，應(yīng)用算符生成第一層節(jié)點，檢查目標(biāo)節(jié)點是否在這些后繼節(jié)點中，若沒有，再用產(chǎn)生式規(guī)則將所有第一層的節(jié)點逐一擴展，得到第二層節(jié)點，并逐一檢查第二層節(jié)點中是否包含目標(biāo)節(jié)點。（二）廣度優(yōu)先搜索遍歷算法一．寬度優(yōu)先搜索的過程寬度優(yōu)先搜索算法（又稱寬度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。兩種方式本質(zhì)上是等價，但兩者也時有區(qū)別的。12. ]13. else if j=規(guī)則數(shù) then Backtracking 14. else brk:=false。8. if New 符合條件 then [9. 產(chǎn)生子節(jié)點New并將其壓棧。5. Repeat6. j:=j+1。4. j:=0。1. dep:=0。2. if dep0 then 取出棧頂元素3. else p:=true。非遞歸算法偽代碼：procedure Backtracking。1. 初始化。7. 棧頂元素出棧。2. for r:=1 to 規(guī)則數(shù) do [3. New:=Expand(N,r)4. if 值節(jié)點New符合條件 then [5. 產(chǎn)生的子節(jié)點New壓入棧。遞歸算法偽代碼：procedure DFS_ recursive(N)。Close(Output)。 Main。ReWrite(Output)。39。ReSet(Input)。39。 end。No answer39。 Recursive。 Best:=MaxN。 List[1].y0:=y。 begin List[1].state:=Source。 procedure Main。 End。 {繼續(xù)搜索} dec(Open)?！ 。迦刖C合數(shù)據(jù)庫｝ List[Open]:=New。 For i:=1 to 4 do begin ?。来芜x用規(guī)則｝ Move(List[Open],i,OK,New)。 Save:=List。 Begin If Open1=Best then exit。 New: tList。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1