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

1、廣度優(yōu)先搜索,引入問(wèn)題why queue,搜索廣度優(yōu)先搜索 隊(duì)列的維護(hù) 什么是隊(duì)列,隊(duì)列,隊(duì)列是限定在一端進(jìn)行插入，另一端進(jìn)行刪除的特殊的線性表。 刪除的一端稱(chēng)為隊(duì)首，插入的一端稱(chēng)為隊(duì)尾。 具體事例：排隊(duì)買(mǎi)票，后來(lái)的人排在隊(duì)尾（插入），隊(duì)首的人離開(kāi)（刪除,隊(duì)列的特點(diǎn),線性 隊(duì)頭讀 隊(duì)尾寫(xiě) 先進(jìn)先出,隊(duì)列的定義,靜態(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,隊(duì)列的基本操作,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)先搜索,在搜索過(guò)程中，我們把每個(gè)狀態(tài)看作是結(jié)點(diǎn)，把狀態(tài)之間的聯(lián)系看做是邊，這樣我們就可以得到一棵樹(shù)，我們把這棵樹(shù)稱(chēng)為“搜索樹(shù),深度、廣度優(yōu)先搜索,初始狀態(tài)對(duì)應(yīng)根結(jié)點(diǎn)，目標(biāo)狀態(tài)對(duì)應(yīng)目標(biāo)結(jié)點(diǎn)。問(wèn)題的一個(gè)解就是一條從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑。 對(duì)“搜索樹(shù)”的搜索算法類(lèi)似于樹(shù)的遍歷，通常有兩種不同的實(shí)現(xiàn)方法： 廣度優(yōu)先搜索(BFS) 深度優(yōu)先搜索(DFS,廣度優(yōu)先搜索,BFS每次都先將搜索樹(shù)某一層的所有節(jié)點(diǎn)全部訪問(wèn)完畢后再訪問(wèn)下一層，因此也被稱(chēng)作“按層搜索,廣度優(yōu)先搜索,一般來(lái)說(shuō)，B

3、FS使用隊(duì)列來(lái)實(shí)現(xiàn)。 BFS一般用來(lái)求最優(yōu)解。 在存儲(chǔ)數(shù)據(jù)時(shí)，除了需要存儲(chǔ)當(dāng)前狀態(tài)外，還需要存儲(chǔ)當(dāng)前狀態(tài)的父狀態(tài)以及由父狀態(tài)轉(zhuǎn)換過(guò)來(lái)所執(zhí)行的操作,廣度優(yōu)先搜索算法,初始狀態(tài)入隊(duì) op := 1 對(duì)隊(duì)首狀態(tài)進(jìn)行操作op，得到新?tīng)顟B(tài)； 檢查此狀態(tài)是否出現(xiàn)過(guò)，如未出現(xiàn)則將此狀態(tài)入隊(duì)； 如果此狀態(tài)為目標(biāo)狀態(tài)，則輸出； 如所有操作都已完成，則隊(duì)首出隊(duì)，否則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還可以擴(kuò)展 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是目標(biāo)狀態(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表示樹(shù)的深度；d表示解的深度；dk,從入口（1）到出口（17）的可行路線圖中，數(shù)字標(biāo)號(hào)表示關(guān)卡： 現(xiàn)將上面的路線圖，按記錄結(jié)構(gòu)存儲(chǔ)如下,隊(duì)列應(yīng)用,請(qǐng)?jiān)O(shè)計(jì)一種能從存儲(chǔ)數(shù)據(jù)中求出從入口到出口經(jīng)過(guò)最少關(guān)卡路徑的算法,從列表中可以看出出口關(guān)卡號(hào)（17）的被訪問(wèn)路徑最短的是：(17)(16)(19)(18)(1)開(kāi)始,關(guān)卡（最短路徑,I：=1 ； WHILE NOI 17 DO I:=I+1 ; REPEAT WRITE(,NOI,); WRITE(); I:=PREI ; UNTIL I=0,編一個(gè)程序，找出一條通過(guò)迷宮的路

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

7、, 總列數(shù)： 0n+1,8個(gè)方向表示可以用數(shù)組說(shuō)明,如何記錄探索的蹤跡？ 隊(duì)列,如何防止重復(fù)探索：將迷宮中的0替換為-1 隊(duì)列中入隊(duì)、出隊(duì)情況如下表,迷宮問(wèn)題,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,迷宮問(wèn)題,其實(shí)本題也可以用深度優(yōu)先搜索來(lái)做，但是正如前面所說(shuō)的，因?yàn)橐笞顑?yōu)解，深度優(yōu)先搜索需要將整個(gè)搜索樹(shù)都搜索完。 寬度優(yōu)先搜索搜到的第一個(gè)解一定

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

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

11、升和7升的容器中各有5升油。 題解 三個(gè)容器可以看作三個(gè)變量 C10，C7，C3，每次倒油的可能性只有如下六種情況： C10 向 C7 倒油 C10 向 C3 倒油 C7 向 C10 倒油 C7 向 C3 倒油 C3 向 C10 倒油 C3 向 C7 倒油,應(yīng)用倒油,從一個(gè)容器狀態(tài)（三個(gè)容器中油的容量）看，雖然有可能經(jīng)過(guò)上述六種倒油的方法產(chǎn)生六種容器狀態(tài)，但實(shí)際上這六種新產(chǎn)生的容器狀態(tài)，許多是已經(jīng)出現(xiàn)過(guò)的狀態(tài)。例如初始狀態(tài)（10,0,0）表示 C10=10，C7=0，C3=0，經(jīng)過(guò)上述六種倒油方法只能產(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,當(dāng)?shù)褂彤a(chǎn)生出第19個(gè)容器狀態(tài)時(shí)已達(dá)到了題解的目的。這時(shí)只要根據(jù)pre中的狀態(tài)號(hào)17可以回溯到第17個(gè)容器狀態(tài)的pre值為15，依次可再獲得13，11，9，7，5，2，1容器狀態(tài)號(hào)，從而即可得到解題的倒油過(guò)程（共倒9次）。 注意,從一個(gè)容器中向另一個(gè)容器中倒油,人操作是很直觀的,對(duì)編程來(lái)說(shuō)則必須考慮: 1) 有沒(méi)有油可倒? 2) 究竟倒多少?可能要全部倒入另一容器,也可能只要倒一部分另一容器已經(jīng)滿了,廣度優(yōu)先搜索的局限,對(duì)于BFS而言，當(dāng)求解步驟較長(zhǎng)時(shí)，由于需要存儲(chǔ)全部的擴(kuò)展結(jié)點(diǎn)，很容易造成空間不夠的情況。 對(duì)于這種情況，往往會(huì)通過(guò)剪枝減去不可能的狀態(tài)，節(jié)約空間；或者在容許的情況下使用循環(huán)隊(duì)列；或者采用別的方法來(lái)解決問(wèn)題,1假設(shè)在周末舞會(huì)上，男士們和女士們進(jìn)入舞廳時(shí)，各自排成一隊(duì)。跳舞開(kāi)始時(shí)，依次從男隊(duì)和女隊(duì)的隊(duì)頭上各出一人配成舞伴。若兩隊(duì)初始人數(shù)不相同，則較長(zhǎng)的那一隊(duì)中未