資源描述：
《廣度優(yōu)先搜索Pascal.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、廣度優(yōu)先搜索的過(guò)程廣度優(yōu)先搜索算法（又稱寬度優(yōu)先搜索）是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。廣度優(yōu)先算法的核心思想是：從初始節(jié)點(diǎn)開始，應(yīng)用算符生成第一層節(jié)點(diǎn)，檢查目標(biāo)節(jié)點(diǎn)是否在這些后繼節(jié)點(diǎn)中，若沒(méi)有，再用產(chǎn)生式規(guī)則將所有第一層的節(jié)點(diǎn)逐一擴(kuò)展，得到第二層節(jié)點(diǎn)，并逐一檢查第二層節(jié)點(diǎn)中是否包含目標(biāo)節(jié)點(diǎn)。若沒(méi)有，再用算符逐一擴(kuò)展第二層的所有節(jié)點(diǎn)……，如此依次擴(kuò)展，檢查下去，直到發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)為止。即⒈從圖中的某一頂點(diǎn)V0開始，先訪問(wèn)V0
2、；⒉訪問(wèn)所有與V0相鄰接的頂點(diǎn)V1，V2，......，Vt；⒊依次訪問(wèn)與V1，V2，......，Vt相鄰接的所有未曾訪問(wèn)過(guò)的頂點(diǎn)；⒋循此以往，直至所有的頂點(diǎn)都被訪問(wèn)過(guò)為止。這種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)長(zhǎng)的趨勢(shì)，所以稱之為廣度優(yōu)先搜索。廣度優(yōu)先搜索算法描述：ProgramBfs；初始化，初始狀態(tài)存入隊(duì)列；隊(duì)列首指針head:=0;尾指針tail:=1；repeat指針head后移一位，指向待擴(kuò)展結(jié)點(diǎn)；forI=1tomaxdo//max為產(chǎn)生子結(jié)點(diǎn)的規(guī)則數(shù)beginif子結(jié)點(diǎn)符合條件thenbegintail指針增1，把新結(jié)點(diǎn)存入列尾；
3、if新結(jié)點(diǎn)與原已產(chǎn)生結(jié)點(diǎn)重復(fù)then刪去該結(jié)點(diǎn)（取消入隊(duì)，tail減1）elseif新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)then輸出并退出；end;end;until(head>=tail);//隊(duì)列為空廣度優(yōu)先搜索注意事項(xiàng)：1、每生成一個(gè)子結(jié)點(diǎn)，就要提供指向它們父親結(jié)點(diǎn)的指針。當(dāng)解出現(xiàn)時(shí)候，通過(guò)逆向跟蹤，找到從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑。當(dāng)然不要求輸出路徑，就沒(méi)必要記父親。2、生成的結(jié)點(diǎn)要與前面所有已經(jīng)產(chǎn)生結(jié)點(diǎn)比較，以免出現(xiàn)重復(fù)結(jié)點(diǎn)，浪費(fèi)時(shí)間，還有可能陷入死循環(huán)。3、如果目標(biāo)結(jié)點(diǎn)的深度與“費(fèi)用”（如：路徑長(zhǎng)度）成正比，那么，找到的第一個(gè)解即為最優(yōu)解，這時(shí)，搜索
4、速度比深度搜索要快些，在求最優(yōu)解時(shí)往往采用廣度優(yōu)先搜索；如果結(jié)點(diǎn)的“費(fèi)用”不與深度成正比時(shí)，第一次找到的解不一定是最優(yōu)解。4、廣度優(yōu)先搜索的效率還有賴于目標(biāo)結(jié)點(diǎn)所在位置情況，如果目標(biāo)結(jié)點(diǎn)深度處于較深層時(shí)，需搜索的結(jié)點(diǎn)數(shù)基本上以指數(shù)增長(zhǎng)。下面我們看看怎樣用寬度優(yōu)先搜索來(lái)解決八數(shù)碼問(wèn)題。例如 圖2給出廣度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹。搜索樹上的所有結(jié)點(diǎn)都標(biāo)記它們所對(duì)應(yīng)的狀態(tài)，每個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示結(jié)點(diǎn)擴(kuò)展的順序。粗線條路徑表明求得的一個(gè)解。從圖中可以看出，擴(kuò)展第２６個(gè)結(jié)點(diǎn)，總共生成４６個(gè)結(jié)點(diǎn)之后，才求得這個(gè)解。此外，直接觀察此圖表明，
5、不存在有更短走步序列的解?！纠?】圖4表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過(guò)若干個(gè)城市。現(xiàn)要找出一條經(jīng)過(guò)城市最少的一條路線。【算法分析】看到這圖很容易想到用鄰接距陣來(lái)表示，0表示能走，1表示不能走。如圖。首先想到的是用隊(duì)列的思想。a數(shù)組是存儲(chǔ)擴(kuò)展結(jié)點(diǎn)的隊(duì)列，a[i].city記錄經(jīng)過(guò)的城市,a[i].pre記錄前趨城市，這樣就可以倒推出最短線路。具體過(guò)程如下：（1）將城市A入隊(duì)，隊(duì)首為0、隊(duì)尾為1。（2）將隊(duì)首所指的城市所有可直通的城市入隊(duì)（如果這個(gè)城市在隊(duì)列中出現(xiàn)過(guò)就不入隊(duì)，可用一個(gè)集合來(lái)判斷），將入隊(duì)城市
6、的pre指向隊(duì)首的位置。然后將隊(duì)首加1，得到新的隊(duì)首城市。重復(fù)以上步驟，直到搜到城市H時(shí)，搜索結(jié)束。利用pre可倒推出最少城市線路?！緟⒖汲绦颉縋rogramEx8_1;constju:array[1..8,1..8]of0..1=((1,0,0,0,1,0,1,1),(0,1,1,1,1,0,1,1),(0,1,1,0,0,1,1,1),(0,1,0,1,1,1,0,1),(1,1,0,1,1,1,0,0),(0,0,1,1,1,1,1,0),(1,1,1,0,0,1,1,0),(1,1,1,1,0,0,0,1)); typenode=re
7、cord//記錄定義city:char;pre:integer;end;varhead,tail,i:integer;a:array[1..100]ofnode;s:setof'A'..'H';procedureout(d:integer);//輸出過(guò)程beginwrite(a[d].city);repeatd:=a[d].pre;write('--',a[d].city); untila[d].pre=0;writeln; end;proceduredoit; beginhead:=0;tail:=1;a[1].city:=‘A’;a[1]
8、.pre:=0;s:=[‘A’];repeat//步驟2inc(head);//隊(duì)首加一，出隊(duì)fori:=1to8do//搜索可直通的城市if（ju[ord(a[h
