資源描述：
《廣度優(yōu)先搜索陳鵬》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、廣度優(yōu)先搜索引入問題——whyqueue搜索——廣度優(yōu)先搜索隊列的維護什么是隊列？隊列隊列是限定在一端進行插入，另一端進行刪除的特殊的線性表。刪除的一端稱為隊首，插入的一端稱為隊尾。具體事例：排隊買票，后來的人排在隊尾（插入），隊首的人離開（刪除）。隊列的特點線性隊頭讀隊尾寫先進先出隊列的定義靜態(tài)—數組Typearr=array[1..n]ofinteger;queue=recordvec:arr;front,rear:integer;end;Varq:queue;Varqueue:arr;front,rear:integer;隊列的基本操作操作靜態(tài)數組(A,
2、f,r)建立空隊列測試隊列是否為空入隊(insert)出隊(dele)尾插法F:=0;r:=0F>rR:=r+1;a[r]:=x;Iff=0thenf:=1;X:=a[f];f:=f+1;和約定有關深度、廣度優(yōu)先搜索在搜索過程中，我們把每個狀態(tài)看作是結點，把狀態(tài)之間的聯系看做是邊，這樣我們就可以得到一棵樹，我們把這棵樹稱為“搜索樹”。深度、廣度優(yōu)先搜索初始狀態(tài)對應根結點，目標狀態(tài)對應目標結點。問題的一個解就是一條從根結點到目標結點的路徑。對“搜索樹”的搜索算法類似于樹的遍歷，通常有兩種不同的實現方法：廣度優(yōu)先搜索(BFS)深度優(yōu)先搜索(DFS)廣度優(yōu)先搜索BF
3、S每次都先將搜索樹某一層的所有節(jié)點全部訪問完畢后再訪問下一層，因此也被稱作“按層搜索”。廣度優(yōu)先搜索一般來說，BFS使用隊列來實現。BFS一般用來求最優(yōu)解。在存儲數據時，除了需要存儲當前狀態(tài)外，還需要存儲當前狀態(tài)的父狀態(tài)以及由父狀態(tài)轉換過來所執(zhí)行的操作。DataOPPre廣度優(yōu)先搜索算法初始狀態(tài)入隊op:=1對隊首狀態(tài)進行操作op，得到新狀態(tài)；檢查此狀態(tài)是否出現過，如未出現則將此狀態(tài)入隊；如果此狀態(tài)為目標狀態(tài)，則輸出；如所有操作都已完成，則隊首出隊，否則op:=op+1，返回(3)。廣度優(yōu)先搜索的程序框架procedurebfs;beginhead:=0;ta
4、il:=1;data[tail].data:=初始狀態(tài);data[tail].op:=0;data[tail].pre:=0;flag:=false;repeatinc(head);whiledata[head]還可以擴展dobeginnew:=op(data[head].state);ifnew已經出現thencontinue;inc(tail);data[tail].data:=new;data[tail].op:=op;data[tail].pre:=head;ifnew是目標狀態(tài)thenbeginflag:=true;break;end;end;unt
5、il(tail=head)orflagifflagthenoutputelsewriteln('NoAnswer');end;DFSorBFS搜索方式時間空間適用問題DFSO(ck)O(k)必須完全遍歷或不要求解的深度最小BFSO(cd)O(cd)解靠近根或要求解的深度最小k表示樹的深度；d表示解的深度；d≤k從入口（1）到出口（17）的可行路線圖中，數字標號表示關卡：現將上面的路線圖，按記錄結構存儲如下：隊列應用請設計一種能從存儲數據中求出從入口到出口經過最少關卡路徑的算法。從列表中可以看出出口關卡號（17）的被訪問路徑最短的是：(17)←(16)←(19)
6、←(18)←(1)←開始關卡（最短路徑）I：=1；WHILENO[I]<>17DOI:=I+1;REPEATWRITE(‘(‘,NO[I],’)’);WRITE(‘←’);I:=PRE[I];UNTILI=0；編一個程序，找出一條通過迷宮的路徑。這里有黑色方塊的單元表示走不通，將一只老鼠從入口處經過迷宮到出口處的通路一一打印出來。迷宮問題010000001000010001100000111001100000000000011入口→→出口大?。?5入口:21出口84則路徑如(2)**********....*入口$$$$****.****$**...**.$$
7、**..***.$***...**.$$****.****$**...**..$*└──出口(1)(2)迷宮問題---找出一個從入口到出口的最短路徑（八個方向）01110111101010100100111101110011100110000110011011111111111011101111110101010110100111111011100111110011000110110011011111111111總行數：0——m+1,總列數：0——n+18個方向表示可以用數組說明：10121131041-150-16-1-17-108-11如何記錄探索的蹤跡？
8、——隊列序號123456X123332
