資源描述：
《廣度優(yōu)先搜索97439》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、廣度優(yōu)先搜索算法一．寬度優(yōu)先搜索的過程寬度優(yōu)先搜索算法是最簡便和常用的圖形搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。寬度優(yōu)先算法的核心思想是：從初始節(jié)點開始，應用算符生成第一層節(jié)點，檢查目標節(jié)點是否在這些后繼節(jié)點中，若沒有，再用產生式規(guī)則將所有第一層的節(jié)點逐一擴展，得到第二層節(jié)點，并逐一檢查第二層節(jié)點中是否包含目標節(jié)點。若沒有，再用算符逐一擴展第二層的所有節(jié)點……，如此依次擴展，檢查下去，直到發(fā)現(xiàn)目標節(jié)點為止。即1、從圖中的某一頂點V0開始，先訪問V0；2、訪問所有與V0相
2、鄰接的頂點V1，V2，......，Vt；3、依次訪問與V1，V2，......，Vt相鄰接的所有未曾訪問過的頂點；4、循此以往，直至所有的頂點都被訪問過為止。5、這種搜索的次序體現(xiàn)沿層次向橫向擴長的趨勢，所以稱之為廣度優(yōu)先搜索。對同一層結點來說，一般按先生成先擴展的順序進行，因此在數(shù)據(jù)結構上引入了“隊列”結構?！瓣犃小笔且环N線性表，具有先進先出的特點，對于它所有的插入和刪除操作分別僅在隊列尾和隊列首進行。二、廣度優(yōu)先搜索算法描述：ProgramBfs；初始化，初始狀態(tài)存入OPEN表；隊列首指針head:=0;尾指針tail:=1；repeat指針head后移一位，指向待
3、擴展結點；forI=1tomaxdo{max為產生子結點的規(guī)則數(shù)}beginif子結點符合條件thenbegintail指針增1，把新結點存入列尾；if新結點與原已產生結點重復then刪去該結點（取消入隊，tail減1）elseif新結點是目標結點then輸出并退出；end;end;until(tail>=head);{隊列空}三、廣度優(yōu)先搜索注意事項：1、每生成一個子結點，就要提供指向它們父親結點的指針。當解出現(xiàn)時候，通過逆向跟蹤，找到從根結點到目標結點的一條路徑。2、生成的結點要與前面所有已經產生結點比較，以免出現(xiàn)重復結點，浪費時間，還有可能陷入死循環(huán)。3、如果目標結
4、點的深度與“費用”（如：路徑長度）成正比，那么，找到的第一個解即為最優(yōu)解，這時，搜索速度比深度搜索要快些；如果結點的“費用”第12頁共12頁不與深度成正比時，第一次找到的解不一定是最優(yōu)解。4、廣度優(yōu)先搜索的效率還有賴于目標結點所在位置情況，如果目標結點深度處于較深層時，需搜索的結點數(shù)基本上以指數(shù)增長。下面我們看看怎樣用寬度優(yōu)先搜索來解決八數(shù)碼問題。例如 圖2給出廣度優(yōu)先搜索應用于八數(shù)碼難題時所生成的搜索樹。搜索樹上的所有結點都標記它們所對應的狀態(tài)，每個結點旁邊的數(shù)字表示結點擴展的順序。粗線條路徑表明求得的一個解。從圖中可以看出，擴展２６個結點和生成４６個結點之后，才求得這
5、個解。此外，直接觀察此圖表明，不存在有更短走步序列的解。 圖2 廣度優(yōu)先搜索圖 程序實現(xiàn)算法： ProgramBFS； 建立數(shù)據(jù)庫data；數(shù)據(jù)庫賦初值； 設隊列頭指針H:=0；隊列尾指針L:=1； repeat 取下一個H所指的結點； fori:=1tomaxdo{i為產生新結點規(guī)則編號} begin L增1，把新結點存入數(shù)據(jù)庫隊尾；記錄父結點的位置； if新結點與原有結點重復then 刪去該結點(L減1) else
6、 if新結點為目標結點then輸出并退出； end； end； untilH>=L{隊列為空}程序：第12頁共12頁program8no_bfs;{八數(shù)碼的寬度優(yōu)先搜索算法}ConstDir:array[1..4,1..2]ofinteger {四種移動方向，對應產生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));N=10000;TypeT8No=array[1..3,1..3]ofinteger;TList=recordFather:integer; {父指針}dep:byte; {深度}X0,
7、Y0:byte;{0的位置}State:T8No; {棋盤狀態(tài)}end;VarSource,Target:T8No;List:array[0..10000]ofTList;{綜合數(shù)據(jù)庫}Closed,Open,Best:integer{Best表示最優(yōu)移動次數(shù)}Answer:integer;{記錄解}Found:Boolean;{解標志}procedureGetInfo;{讀入初始和目標節(jié)點}vari,j:integer;beginfori:=1to3doforj:=1to3doread(Source[i,j
