第八章 廣度優(yōu)先搜索算法.ppt

1、第八章 廣度優(yōu)先搜索算法,廣度優(yōu)先搜索算法是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。如Dijkstra單源最短路徑和Prim最小生成樹(shù)算法都采用了廣度優(yōu)先搜索的思想。 核心思想：從初始節(jié)點(diǎn)開(kāi)始，應(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)為止。即： 1、從圖中的某一頂點(diǎn)v0開(kāi)始，先訪問(wèn)v0； 2、訪問(wèn)所有與v0相鄰接的頂點(diǎn)v1、v2； 3、依次訪問(wèn)與v1、v2vt相鄰接的

2、所有未曾訪問(wèn)過(guò)的頂點(diǎn)； 4、循此以往，直到所有的頂點(diǎn)都被訪問(wèn)過(guò)為止。 這種搜索的次序體現(xiàn)了沿層次向橫向擴(kuò)展的趨勢(shì)，所以稱之為廣度優(yōu)先搜索。,【模塊1】 Program bfs; 初始化，初始狀態(tài)存入隊(duì)列； 隊(duì)列首指針head:=0; 尾指針tail:=1; while headtail do begin inc（head）；指針head后移一位，指向待擴(kuò)展節(jié)點(diǎn)； for i:=1 to max do begin if 新節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn) then 輸出并退出； if 新節(jié)點(diǎn)符合條件，并且新節(jié)點(diǎn)與原已產(chǎn)生的節(jié)點(diǎn)不重復(fù) then tail指針加1，把新節(jié)點(diǎn)加入到隊(duì)尾； end； end；,算法描述模

3、塊（運(yùn)用了隊(duì)列的結(jié)構(gòu)）,【模塊2】 Program bfs; 初始化，初始狀態(tài)存入隊(duì)列； 隊(duì)列首指針head:=0; 尾指針tail:=1; repeat inc（head）； 指針head后移一位，指向待擴(kuò)展節(jié)點(diǎn)； for i:=1 to max do begin if 新節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn) then 輸出并退出； if 新節(jié)點(diǎn)符合條件，并且新節(jié)點(diǎn)與原已產(chǎn)生的節(jié)點(diǎn)不重復(fù) then tail指針加1，把新節(jié)點(diǎn)加入到隊(duì)尾； end； until head=tail； end；,【廣度優(yōu)先搜索注意事項(xiàng)】 1、每生成一個(gè)子節(jié)點(diǎn)，就要提供指向它們父親節(jié)點(diǎn)的指針。當(dāng)解出現(xiàn)時(shí)候，通過(guò)逆向跟蹤，可以找到從根節(jié)點(diǎn)

4、到目標(biāo)節(jié)點(diǎn)的一條路徑。（當(dāng)然不要求輸出路徑的，就沒(méi)必要記住父親節(jié)點(diǎn)）； 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í)，搜索速度比深度搜索要快些，在求最優(yōu)解時(shí)往往采用廣度優(yōu)先搜索；如果節(jié)點(diǎn)的費(fèi)用不與深度成正比時(shí)，第一次找到的解不一定是最優(yōu)解。,【算法分析】看圖很容易想到用鄰接矩陣來(lái)存儲(chǔ)頂點(diǎn)之間的關(guān)系，0表示有通路，即有邊；1表示沒(méi)有通路，即沒(méi)有邊存在。 定義一個(gè)a數(shù)組，充當(dāng)存儲(chǔ)擴(kuò)展節(jié)點(diǎn)的隊(duì)列，ai.city記錄經(jīng)過(guò)的城市，ai.pre記錄前驅(qū)城市，這樣就

5、可以倒推出最短線路了，具體過(guò)程如下： 1、將城市A入隊(duì)，隊(duì)首指針為0，隊(duì)尾指針為1； 2、將隊(duì)首所指相連的城市依次入隊(duì)（注意的是該城市在隊(duì)列中未曾出現(xiàn)過(guò)），同時(shí)將入隊(duì)城市的pre指向隊(duì)首位置。然后將隊(duì)首指針加1，得到新的隊(duì)首城市。重復(fù)以上操作步驟，直到搜到H城市。利用pre可以倒推出最少城市線路。,例1 如圖 是從 城市A到城市H 的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過(guò)若干個(gè)城市?，F(xiàn)在要找出一條經(jīng)過(guò)城市最少的一條路線。,矩陣存儲(chǔ)頂點(diǎn)關(guān)系,【參考程序】 Program ex_1; const ju:array1.8,1.8 of 0.1=( (1,0,0,0,1,0,1,1), (0,

6、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); type node=record city:char; pre:integer; end; var head,tail,i:integer; a:array1.100 of node; s:arrayA.H of boolean; procedure print(d:integer); begin write(ad.city); repe

7、at d:=ad.pre; write(-,ad.city); until ad.pre=0; end;,Procedure doit; begin fillchar(s,sizeof(s),true); head:=0; tail:=1; a1.city:=A; a1.pre:=0;sa1.city:=false; repeat inc(head); for i:=1 to 8 do if (juord(ahead.city)-64,i=0)and (schr(i+64)=true) then begin inc(tail); atail.city:=chr(i+64); atail.pre

8、:=head; satail.city:=false; if atail.city=H then begin print(tail); break; end; end; until head=tail; end; Begin doit; End.,【算法分析】 1、讀入m*n矩陣陣列，將其轉(zhuǎn)換成為boolean矩陣存入bz數(shù)組中； 2、沿bz數(shù)組矩陣從上到下、從左到右，找到遇到的第一個(gè)細(xì)胞； 3、將細(xì)胞的位置入隊(duì)h，并沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置bz數(shù)組置為false； 4、將h隊(duì)頭出隊(duì)，沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置bz數(shù)組置為false

9、； 5、重復(fù)4，直到h隊(duì)空為止，則此時(shí)找到了一個(gè)細(xì)胞； 6、重復(fù)2，直至矩陣找不到細(xì)胞； 7、輸出找到的細(xì)胞個(gè)數(shù)。,例2 一矩形陣列由數(shù)字0-9組成，數(shù)字1-9代表細(xì)胞，細(xì)胞的定義是沿細(xì)胞數(shù)字上、下、左、右如果還是細(xì)胞數(shù)字則為同一細(xì)胞，求給定矩形陣列的細(xì)胞個(gè)數(shù)。,如陣列： 10 0234500067 1034560500 2045600671 0000000089,【參考程序】 program cell; const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1.1=(0,1,0,-1); var name,s:string; n,m,i,

10、j,num:integer; pic:array1.50,1.50 of integer; bz:array1.50,1.50 of boolean; h:array1.1000,1.2 of integer; procedure doit(p,q:integer); var i,t,w,x,y:integer; begin inc(num);bzp,q:=false; t:=1;w:=1;h1,1:=p;h1,2:=q; repeat for i:=1 to 4 do begin x:=ht,1+dxi;y:=ht,2+dyi; if (x0)and(x0)and(yw; end;,begi

11、n fillchar(bz,sizeof(bz),true); num:=0; readln(m,n); for i:=1 to m do begin readln(s); for j:=1 to n do begin pici,j:=ord(sj)-48; if pici,j=0 then bzi,j:=false; end; end; for i:=1 to m do for j:=1 to n do if bzi,j then doit(i,j); writeln(num); end.,上機(jī)練習(xí),1、最短路徑 如圖，從入口（1）到出口（17）的可行路線圖中，數(shù)字標(biāo)號(hào)表示關(guān)卡。請(qǐng)編程求從入

12、口到出口經(jīng)過(guò)最少關(guān)卡路徑的算法。,提示：用鄰接矩陣存儲(chǔ)關(guān)卡之間的關(guān)系與前驅(qū)。 【輸出樣例】 171619181,2、迷宮問(wèn)題 如圖，給一個(gè)n*m的迷宮圖和一個(gè)入口、一個(gè)出口。編程打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），黃色單元表示可以走（用0表示），只能往上、下、左、右四個(gè)方向走，如果無(wú)路則輸出“No way！”。（注：只輸出一條就可以了） 【提示】本題深搜和廣搜都可以，請(qǐng)同學(xué)們動(dòng)動(dòng)腦子，有條件的可以兩種方法都試試看。,program exp2; const maxn=50; dx:array1.4 of integer=(1,0,-1,0); dy:arr

13、ay1.4 of integer=(0,1,0,-1); var map:array1.maxn,1.maxn of integer; f:boolean; n,m,i,j,desx,desy,soux,souy,head,tail,x,y,k:integer; route:array1.maxn of record x,y,pre:integer;end; procedure print(d:integer); begin if routed.pre0 then begin print(routed.pre);inc(k);end; write(,routed.x,routed.y,) );

14、 end; begin readln(n,m); for i:=1 to n do for j:=1 to m do read(mapi,j); readln(soux,souy); readln(desx,desy);,f:=false;k:=1;head:=0;tail:=1;route1.x:=soux; route1.y:=souy;route1.pre:=0;mapsoux,souy:=-1; repeat inc(head); for i:=1 to 4 do begin x:=routehead.x+dxi; y:=routehead.y+dyi; if (x0)and(x0)a

15、nd(y=m)and(mapx,y=0) then begin inc(tail); routetail.x:=x;routetail.y:=y;routetail.pre:=head; mapx,y:=-1; if (x=desx)and(y=desy) then begin f:=true; print(tail); break; end; end; end; writeln; if f then begin writeln(k);break;end; until head=tail; if not f then writeln(No way!); end.,3、硬幣翻轉(zhuǎn) 在桌面上有一排硬幣，共n枚，每一枚硬幣均為正面向上?，F(xiàn)在要把所有的硬幣翻成反面向上，規(guī)則是每次可翻轉(zhuǎn)任意n-1枚硬幣（正面向上的被翻轉(zhuǎn)為反面向上，反之亦然）。求一個(gè)最短的操作序列（將每次翻轉(zhuǎn)n-1枚硬幣定為一次操作