資源描述：
《廣度優(yōu)先搜索.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、廣度優(yōu)先搜索廣度優(yōu)先搜索動畫引入問題——whyqueue搜索——廣度優(yōu)先搜索隊列的維護(hù)什么是隊列？2廣度優(yōu)先搜索動畫隊列隊列是限定在一端進(jìn)行插入，另一端進(jìn)行刪除的特殊的線性表。刪除的一端稱為隊首，插入的一端稱為隊尾。具體事例：排隊買票，后來的人排在隊尾（插入），隊首的人離開（刪除）。3廣度優(yōu)先搜索動畫隊列的特點線性隊頭讀隊尾寫先進(jìn)先出4廣度優(yōu)先搜索動畫隊列的定義靜態(tài)—數(shù)組Typearr=array[1..n]ofinteger;queue=recordvec:arr;front,rear:integer;end;Varq:queue;Varq
2、ueue:arr;front,rear:integer;5廣度優(yōu)先搜索動畫隊列的基本操作操作靜態(tài)數(shù)組(A,f,r)建立空隊列測試隊列是否為空入隊(insert)出隊(dele)尾插法F:=0;r:=0F>rR:=r+1;a[r]:=x;Iff=0thenf:=1;X:=a[f];f:=f+1;和約定有關(guān)6廣度優(yōu)先搜索動畫深度、廣度優(yōu)先搜索在搜索過程中，我們把每個狀態(tài)看作是結(jié)點，把狀態(tài)之間的聯(lián)系看做是邊，這樣我們就可以得到一棵樹，我們把這棵樹稱為“搜索樹”。7廣度優(yōu)先搜索動畫深度、廣度優(yōu)先搜索初始狀態(tài)對應(yīng)根結(jié)點，目標(biāo)狀態(tài)對應(yīng)目標(biāo)結(jié)點。問題的一個
3、解就是一條從根結(jié)點到目標(biāo)結(jié)點的路徑。對“搜索樹”的搜索算法類似于樹的遍歷，通常有兩種不同的實現(xiàn)方法：廣度優(yōu)先搜索(BFS)深度優(yōu)先搜索(DFS)8廣度優(yōu)先搜索動畫廣度優(yōu)先搜索BFS每次都先將搜索樹某一層的所有節(jié)點全部訪問完畢后再訪問下一層，因此也被稱作“按層搜索”。9廣度優(yōu)先搜索動畫廣度優(yōu)先搜索一般來說，BFS使用隊列來實現(xiàn)。BFS一般用來求最優(yōu)解。在存儲數(shù)據(jù)時，除了需要存儲當(dāng)前狀態(tài)外，還需要存儲當(dāng)前狀態(tài)的父狀態(tài)以及由父狀態(tài)轉(zhuǎn)換過來所執(zhí)行的操作。DataOPPre10廣度優(yōu)先搜索動畫廣度優(yōu)先搜索算法初始狀態(tài)入隊op:=1對隊首狀態(tài)進(jìn)行操作op
4、，得到新狀態(tài)；檢查此狀態(tài)是否出現(xiàn)過，如未出現(xiàn)則將此狀態(tài)入隊；如果此狀態(tài)為目標(biāo)狀態(tài)，則輸出；如所有操作都已完成，則隊首出隊，否則op:=op+1，返回(3)。11廣度優(yōu)先搜索動畫廣度優(yōu)先搜索算法描述ProgramBfs；初始化，初始狀態(tài)存入OPEN表(即隊列)；隊列首指針head:=0;尾指針tail:=1；repeat指針head后移一位，指向待擴展結(jié)點；forI=1tomaxdo{max為產(chǎn)生子結(jié)點的規(guī)則數(shù)}beginif子結(jié)點符合條件thenbegintail指針增1，把新結(jié)點存入列尾；if新結(jié)點與原已產(chǎn)生結(jié)點重復(fù)then刪去該結(jié)點（取消
5、入隊，tail減1）elseif新結(jié)點是目標(biāo)結(jié)點then輸出并退出；end;end;until(head>=tail);{隊列空}12廣度優(yōu)先搜索動畫初始化LIST取消在N中結(jié)點的所有標(biāo)記;標(biāo)記結(jié)點s1245369781pred(1)=0next:=1 order(next)=1LIST:={1}next11245369781113廣度優(yōu)先搜索動畫在LIST中選擇結(jié)點iLIST在廣度優(yōu)先搜索中，i是在LIST中的第一個結(jié)點12453697811next11114廣度優(yōu)先搜索動畫如果結(jié)點i和一條可進(jìn)入弧關(guān)聯(lián)…LIST選擇一條可進(jìn)入弧(i,j)1
6、2453697811next1211標(biāo)記結(jié)點jpred(j):=i2Next:= Next+1order(j):=next把j添加到LIST2215廣度優(yōu)先搜索動畫如果結(jié)點i和一條可進(jìn)入的弧關(guān)聯(lián)…LIST選擇一條可進(jìn)入弧(i,j)124536978311next2311標(biāo)記結(jié)點jpred(j):=i2Next:= Next+1order(j):=next把j添加到LIST225516廣度優(yōu)先搜索動畫4如果結(jié)點i和一條可進(jìn)入的弧關(guān)聯(lián)…LIST選擇一條可進(jìn)入弧(i,j)124536978311next2311標(biāo)記結(jié)點jpred(j):=i2Nex
7、t:= Next+1order(j):=next把j添加到LIST225534317廣度優(yōu)先搜索動畫4如果結(jié)點i和一條可進(jìn)入的弧關(guān)聯(lián)…LIST從LIST刪除結(jié)點i124536978311next231122255343118廣度優(yōu)先搜索動畫4選擇結(jié)點iLIST在LIST上的第一個結(jié)點變成了結(jié)點i124536978311next2311222553431219廣度優(yōu)先搜索動畫54如果結(jié)點i和一條可進(jìn)入的弧關(guān)聯(lián)…LIST124536978311next231222553432選擇一條可進(jìn)入弧arc(i,j)標(biāo)記結(jié)點jpred(j):=iNext:
8、= Next+1order(j):=next把j添加到LIST45420廣度優(yōu)先搜索動畫54如果結(jié)點i和一條可進(jìn)入的弧關(guān)聯(lián)…LIST124536978311next
