廣度優(yōu)先搜索陳鵬ppt課件

1、廣度優(yōu)先搜索,引入問題why queue,搜索廣度優(yōu)先搜索 隊列的維護 什么是隊列,隊列,隊列是限定在一端進行插入，另一端進行刪除的特殊的線性表。 刪除的一端稱為隊首，插入的一端稱為隊尾。 具體事例：排隊買票，后來的人排在隊尾（插入），隊首的人離開（刪除,隊列的特點,線性 隊頭讀 隊尾寫 先進先出,隊列的定義,靜態(tài)數(shù)組 Type arr=array1.n of integer; queue=record vec:arr; front,rear:integer; end; Var q:queue,Var queue:arr; front,rear:integer,隊列的基本操作,F:=0;r:=

2、0,Fr,R:=r+1;ar:=x; If f=0 then f:=1,X:=af;f:=f+1,和約定有關(guān),深度、廣度優(yōu)先搜索,在搜索過程中，我們把每個狀態(tài)看作是結(jié)點，把狀態(tài)之間的聯(lián)系看做是邊，這樣我們就可以得到一棵樹，我們把這棵樹稱為“搜索樹,深度、廣度優(yōu)先搜索,初始狀態(tài)對應根結(jié)點，目標狀態(tài)對應目標結(jié)點。問題的一個解就是一條從根結(jié)點到目標結(jié)點的路徑。 對“搜索樹”的搜索算法類似于樹的遍歷，通常有兩種不同的實現(xiàn)方法： 廣度優(yōu)先搜索(BFS) 深度優(yōu)先搜索(DFS,廣度優(yōu)先搜索,BFS每次都先將搜索樹某一層的所有節(jié)點全部訪問完畢后再訪問下一層，因此也被稱作“按層搜索,廣度優(yōu)先搜索,一般來說，B

3、FS使用隊列來實現(xiàn)。 BFS一般用來求最優(yōu)解。 在存儲數(shù)據(jù)時，除了需要存儲當前狀態(tài)外，還需要存儲當前狀態(tài)的父狀態(tài)以及由父狀態(tài)轉(zhuǎn)換過來所執(zhí)行的操作,廣度優(yōu)先搜索算法,初始狀態(tài)入隊 op := 1 對隊首狀態(tài)進行操作op，得到新狀態(tài)； 檢查此狀態(tài)是否出現(xiàn)過，如未出現(xiàn)則將此狀態(tài)入隊； 如果此狀態(tài)為目標狀態(tài)，則輸出； 如所有操作都已完成，則隊首出隊，否則op := op + 1，返回(3,廣度優(yōu)先搜索的程序框架,procedure bfs; begin head := 0; tail := 1; datatail.data := 初始狀態(tài); datatail.op := 0; datatail.pre

4、 := 0; flag := false; repeat inc(head); while datahead還可以擴展 do begin new := op(datahead.state); if new已經(jīng)出現(xiàn) then continue; inc(tail); datatail.data := new; datatail.op := op; datatail.pre := head; if new是目標狀態(tài) then begin flag := true; break; end; end; until (tail = head) or flag if flag then output el

5、se writeln(No Answer); end,DFS or BFS,k表示樹的深度；d表示解的深度；dk,從入口（1）到出口（17）的可行路線圖中，數(shù)字標號表示關(guān)卡： 現(xiàn)將上面的路線圖，按記錄結(jié)構(gòu)存儲如下,隊列應用,請設(shè)計一種能從存儲數(shù)據(jù)中求出從入口到出口經(jīng)過最少關(guān)卡路徑的算法,從列表中可以看出出口關(guān)卡號（17）的被訪問路徑最短的是：(17)(16)(19)(18)(1)開始,關(guān)卡（最短路徑,I：=1 ； WHILE NOI 17 DO I:=I+1 ; REPEAT WRITE(,NOI,); WRITE(); I:=PREI ; UNTIL I=0,編一個程序，找出一條通過迷宮的路

6、徑。這里有黑色方塊的單元表示走不通，將一只老鼠從入口處經(jīng)過迷宮到出口處的通路一一打印出來,迷宮問題,入口 出口,大?。?8 5 入口: 2 1 出口 8 4 則路徑如 ( 2 ) * * * * * * * * * * . . . . * 入口 $ $ $ $ * * * * . * * * * $ * * . . . * * . $ $ * * . . * * * . $ * * * . . . * * . $ $ * * * * . * * * * $ * * . . . * * . . $ * 出口 ( 1 ) ( 2,迷宮問題-找出一個從入口到出口的最短路徑（八個方向,總行數(shù)：0m+1

7、, 總列數(shù)： 0n+1,8個方向表示可以用數(shù)組說明,如何記錄探索的蹤跡？ 隊列,如何防止重復探索：將迷宮中的0替換為-1 隊列中入隊、出隊情況如下表,迷宮問題,sq1.x:=1 ;sq1.y:=1 ;sq1.pre:=0 ; front :=1; rear :=1 ; mg1,1:=-1 ; while front=rear do x:=sqfront.x ; y:= sqfront.y ; for v:=1 to 8 do I:=x+zv.x ; j:= y+zv.y ; if mgI,j =0 then rear :=rear+1 ; sqrear.pre:=front ; sqrear.

8、x:=I ; sqrear.y:=j ; mgI,j:= -1 ; if ( i=m ) and (j=n) then print; front := front+1,打印最短路徑,打印最短路徑： Procedure print (var sq : sqtype;rear :integer) ; begin k:=rear ; repeat writeln(,sqk.x,sqk.y,); k:=sqk.pre ; until k=0 ; end,迷宮問題,其實本題也可以用深度優(yōu)先搜索來做，但是正如前面所說的，因為要求最優(yōu)解，深度優(yōu)先搜索需要將整個搜索樹都搜索完。 寬度優(yōu)先搜索搜到的第一個解一定

9、是最優(yōu)解，所以找到解后就可以停止了,應用,現(xiàn)要找出一條從A到H經(jīng)過城市最少的一條路徑,廣度優(yōu)先遍歷: A,具體過程如下： （1） 將城市A入隊，隊首、隊尾都為1。 （2） 將隊首所指的城市所有可直通的城市入隊（如何判斷？），將入隊城市的pre指向隊首的位置。然后將隊首加1，得到新的隊首城市。重復以上步驟，直到城市H入隊為止。當搜到城市H時，搜索結(jié)束。利用pre可倒推出最少城市線路,AH,寬搜基本框架,F,r,隊列初始化； While f=r do 取隊首； 擴展+判重+入隊,給出一個整數(shù)n（n2000）和k個變換規(guī)則（k15） 規(guī)則： 1個數(shù)字可以變換成另1個數(shù)字； 規(guī)則中，右邊的數(shù)字不能為零

10、。 例如：n=234，k=2規(guī)則為 2 5 3 6 234經(jīng)過變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)） 234 534 264 564求經(jīng)過任意次的變換（0次或多次），能產(chǎn)生出多少個不同的整數(shù)。僅要求輸出不同整數(shù)個數(shù),應用產(chǎn)生數(shù),問題分析】 本題考察了同學們?nèi)矫娴哪芰Γ?數(shù)的表示，如何處理； 轉(zhuǎn)換規(guī)則如何表示； 隊列的應用，包括入隊、出隊以及隊的查找。 注意點： 數(shù)以字符串的形式輸入，為了計算方便，經(jīng)過類型轉(zhuǎn)換存入整型數(shù)組中； 對數(shù)的比較也很困難，只能逐位比較，處理時用一個隊列q，開始時隊列q中只有n,有10升油在10升的容器中，另有兩個7升和3升的空容器，現(xiàn)要求用這三個容器倒油，使得最后在10

11、升和7升的容器中各有5升油。 題解 三個容器可以看作三個變量 C10，C7，C3，每次倒油的可能性只有如下六種情況： C10 向 C7 倒油 C10 向 C3 倒油 C7 向 C10 倒油 C7 向 C3 倒油 C3 向 C10 倒油 C3 向 C7 倒油,應用倒油,從一個容器狀態(tài)（三個容器中油的容量）看，雖然有可能經(jīng)過上述六種倒油的方法產(chǎn)生六種容器狀態(tài)，但實際上這六種新產(chǎn)生的容器狀態(tài)，許多是已經(jīng)出現(xiàn)過的狀態(tài)。例如初始狀態(tài)（10,0,0）表示 C10=10，C7=0，C3=0，經(jīng)過上述六種倒油方法只能產(chǎn)生出兩種新的容器狀態(tài)（3,7,0）和（7,0,3,1 2 3 4 5 6 7 8 9 10

12、11 12 13 14 15 16 17 18 19,C10 C7 C3 PRE,當?shù)褂彤a(chǎn)生出第19個容器狀態(tài)時已達到了題解的目的。這時只要根據(jù)pre中的狀態(tài)號17可以回溯到第17個容器狀態(tài)的pre值為15，依次可再獲得13，11，9，7，5，2，1容器狀態(tài)號，從而即可得到解題的倒油過程（共倒9次）。 注意,從一個容器中向另一個容器中倒油,人操作是很直觀的,對編程來說則必須考慮: 1) 有沒有油可倒? 2) 究竟倒多少?可能要全部倒入另一容器,也可能只要倒一部分另一容器已經(jīng)滿了,廣度優(yōu)先搜索的局限,對于BFS而言，當求解步驟較長時，由于需要存儲全部的擴展結(jié)點，很容易造成空間不夠的情況。 對于這種情況，往往會通過剪枝減去不可能的狀態(tài)，節(jié)約空間；或者在容許的情況下使用循環(huán)隊列；或者采用別的方法來解決問題,1假設(shè)在周末舞會上，男士們和女士們進入舞廳時，各自排成一隊。跳舞開始時，依次從男隊和女隊的隊頭上各出一人配成舞伴。若兩隊初始人數(shù)不相同，則較長的那一隊中未