信息學奧賽廣度搜索課件

《信息學奧賽廣度搜索課件》由會員分享，可在線閱讀，更多相關《信息學奧賽廣度搜索課件（20頁珍藏版）》請在裝配圖網上搜索。

1、廣度搜索在程序設計中的應用深度優先:SLMN F F O P F Q F 廣搜優先:SLOMF PQN FFF“廣搜廣搜”用來解決那類問題用來解決那類問題?用深度優先搜索找最優解時必須搜索完所有路徑，即使一個目標用深度優先搜索找最優解時必須搜索完所有路徑，即使一個目標結點在很淺的樹枝上，也得等到它左邊所有結點均被搜索后才能結點在很淺的樹枝上，也得等到它左邊所有結點均被搜索后才能找到它。用這種方法求某些最優解時，效率比較低。而廣度優先找到它。用這種方法求某些最優解時，效率比較低。而廣度優先搜索，能較好地解決這個問題。搜索，能較好地解決這個問題。廣度優先搜索是最簡便和常用的圖形搜索算法之一，從對圖

2、形的廣度優先搜索是最簡便和常用的圖形搜索算法之一，從對圖形的遍歷來看，遵循遍歷來看，遵循“從淺入深從淺入深”的搜索策略。在這種搜索過程中，的搜索策略。在這種搜索過程中，樹上的結點擴展是沿著深度的樹上的結點擴展是沿著深度的“斷層斷層”進行的，所以這種方法一進行的，所以這種方法一定能保證找到最短（步數最少）的解答序列。在不少題中要求找定能保證找到最短（步數最少）的解答序列。在不少題中要求找到經歷步驟最少而達到目標的方案時，多采用此種搜索方法。到經歷步驟最少而達到目標的方案時，多采用此種搜索方法?！皬V搜廣搜”所用的數據結構所用的數據結構-隊列隊列為了體現先生成先擴展的執行方式又能保留所有生成的結點以

3、待為了體現先生成先擴展的執行方式又能保留所有生成的結點以待進一步擴展，廣度優先搜索在數據結構上引用了進一步擴展，廣度優先搜索在數據結構上引用了“隊列隊列”結構。結構。隊列是一種線性表，具有隊列是一種線性表，具有先進先出先進先出的特點，對于它所有的插入和的特點，對于它所有的插入和刪除操作分別僅在隊列尾和隊列首進行。定義兩個刪除操作分別僅在隊列尾和隊列首進行。定義兩個“指針指針”變量變量head和和tail，分別用來指向隊列的頭和尾。初始結點先入隊，頭，分別用來指向隊列的頭和尾。初始結點先入隊，頭指針指向待擴展結點，每生成一個子結點，則尾指針指針指向待擴展結點，每生成一個子結點，則尾指針tail增

4、加增加1，當前結點的所有子結點均生成后，頭指針向后移動（即加當前結點的所有子結點均生成后，頭指針向后移動（即加1），），位于位于head指針之前的（已被刪除）為已擴展結點，指針之前的（已被刪除）為已擴展結點，tail指向所有指向所有已生成結點的最后一個。若已生成結點的最后一個。若head指針大于指針大于tail指針，表示所有解指針，表示所有解答樹上的結點已產生。如果目標結點仍求出現，說明答樹上的結點已產生。如果目標結點仍求出現，說明“無解無解”。原理解析原理解析headtailsLOMFPQNFFF01122334678廣度優先搜索的算法描述廣度優先搜索的算法描述Procedure BFS初始

5、化，初始狀態存入初始化，初始狀態存入OPEN表；表；隊列首指針隊列首指針head:=0；尾指針；尾指針tail:=1；repeatfor I:=1 to max do /其中，其中，max為產生子結點的規則數為產生子結點的規則數 begin if 子結點符合條件子結點符合條件 then begin tail指針增指針增1，把新結點存入隊列尾；，把新結點存入隊列尾；if 新結點與原已產生的結點重復新結點與原已產生的結點重復 then 刪去該結點（取消入隊，刪去該結點（取消入隊，tail減減1）else if 新結點是目標結點新結點是目標結點 then 輸出并退出；輸出并退出；end endunt

6、il(head=tail);廣度優先搜索的注意事項廣度優先搜索的注意事項（1）每生成一個子結點，就要提供指向它們）每生成一個子結點，就要提供指向它們父親結點的指針。當解出現時，通過逆向跟蹤，父親結點的指針。當解出現時，通過逆向跟蹤，找到從根結點到目標結點的一條路徑。找到從根結點到目標結點的一條路徑。（2）生成的子結點要與前面的所有已產生結）生成的子結點要與前面的所有已產生結點比較，以免出現重復結點，浪費時間，還可點比較，以免出現重復結點，浪費時間，還可能陷入死循環。能陷入死循環。（3）廣度優先搜索的效率還有賴于目標結點）廣度優先搜索的效率還有賴于目標結點所有位置情況，如果目標結點處在比較深的層

7、所有位置情況，如果目標結點處在比較深的層上時，需搜索的結點數基本上以指數增長。上時，需搜索的結點數基本上以指數增長。例例1:電子老鼠闖迷宮電子老鼠闖迷宮電子老鼠闖迷宮。如下圖電子老鼠闖迷宮。如下圖1212方方格圖，找出一條自入口（格圖，找出一條自入口（2，9）到）到出口（出口（11，8）的最短路徑。）的最短路徑。12 /迷宮大小2 9 11 8/起點和終點1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 1 11 0 1 0 1 1 0 0 0 0 0 11 0 1 0 1 1 0 1 1 1 0 11 0 1 0 0 0 0 0 1 0 0 11 0 1

8、 0 1 1 1 1 1 1 1 11 0 0 0 1 0 1 0 0 0 0 11 0 1 1 1 0 0 0 1 1 1 11 0 0 0 0 0 1 0 0 0 0 11 1 1 0 1 1 1 1 0 1 0 11 1 1 1 1 1 1 0 0 1 1 11 1 1 1 1 1 1 1 1 1 1 11 223344455566667788899101112131415152322222125252424161617 1802026262619192727272828輸入:輸出:28數據結構定義：A1.maxn,1.maxn表示鄰接矩陣Father1.maxn*maxn表示隊列Sta

9、te1.maxn*maxn,1.2，1表示當前點的橫坐標，2表示縱坐標，記錄狀態procedure bfs;var tail,head,k,i:integer;begin head:=0;tail:=1;state1,1:=px;state1,2:=py;father1:=0;/初始點狀態 repeat for k:=1 to wayn do if check(statehead,1+dxk,statehead,2+dyk)/擴展子節點 then begin tail:=tail+1;/入隊 fathertail:=head;statetail,1:=statehead,1+dxk;state

10、tail,2:=statehead,2+dyk;astatetail,1,statetail,2:=1;/判重標記 if(statetail,1=qx)and(statetail,2=qy)/是否為目標節點 then begin print(tail);tail:=0;end;end;until head=tail;end;例例2:騎士旅行騎士旅行在一個n*m(m,n=1)and(x=1)and(y=tail;end;例例3:翻幣問題翻幣問題有有N個硬幣個硬幣(6=N=w)and(n-statehead=5-w)/生成子節生成子節點條件點條件 then begin tail:=tail+1;f

11、athertail:=head;statetail:=statehead-w+5-w;for k:=1 to tail-1 do /判重判重 if statek=statetail then begin tail:=tail-1;break;end;if statetail=0 then /判斷是否為目標結點判斷是否為目標結點 begin step:=0;print(tail);tail:=0;end;end;until head=tail;例例4:最優乘車最優乘車 一名旅客最近到一名旅客最近到H城旅游，他很想去城旅游，他很想去S公園游玩，但如果從他所在的飯店公園游玩，但如果從他所在的飯店沒有

12、一路已士可以直接到達沒有一路已士可以直接到達S公園，則他可能要先乘某一路巴士坐幾站，再公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺的另一路巴士下來換乘同一站臺的另一路巴士,這樣換乘幾次后到達這樣換乘幾次后到達S公園。公園?，F在用整數現在用整數1,2,N 給給H城的所有的巴士站編號，約定這名旅客所在飯店城的所有的巴士站編號，約定這名旅客所在飯店的巴士站編號為的巴士站編號為1S公園巴士站的編號為公園巴士站的編號為N。寫一個程序，幫助這名旅客尋找一個最優乘車方案寫一個程序，幫助這名旅客尋找一個最優乘車方案,使他在從飯店乘車到使他在從飯店乘車到S公園的過程中換車的次數最少。公園的過程中換車的次數最少。輸入輸入:3 7 /3條線路條線路,7個車站個車站 6 7 4 7 3 6 1 2 3 5 輸出輸出:2廣度搜索的優化廣度搜索的優化Hash的應用啟發式涵數雙向廣度搜索