-廣度優(yōu)先搜索

第八章廣度優(yōu)先搜索廣度優(yōu)先搜索的過程

廣度優(yōu)先搜索算法（又稱寬度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。廣度優(yōu)先算法的核心思想是：從初始節(jié)點(diǎn)開始，應(yīng)用算符生成第一層節(jié)點(diǎn)，檢查目標(biāo)節(jié)點(diǎn)是否在這些后繼節(jié)點(diǎn)中，若沒有，再用產(chǎn)生式規(guī)則將所有第一層的節(jié)點(diǎn)逐一擴(kuò)展，得到第二層節(jié)點(diǎn)，并逐一檢查第二層節(jié)點(diǎn)中是否包含目標(biāo)節(jié)點(diǎn)。若沒有，再用算符逐一擴(kuò)展第二層的所有節(jié)點(diǎn)……，如此依次擴(kuò)展，檢查下去，直到發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)為止。即⒈從圖中的某一頂點(diǎn)V0開始，先訪問V0；⒉訪問所有與V0相鄰接的頂點(diǎn)V1，V2，......，Vt；⒊依次訪問與V1，V2，......，Vt相鄰接的所有未曾訪問過的頂點(diǎn)；⒋循此以往，直至所有的頂點(diǎn)都被訪問過為止。這種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)長的趨勢，所以稱之為廣度優(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)存入列尾；

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í)候，通過逆向跟蹤，找到從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑。當(dāng)然不要求輸出路徑，就沒必要記父親。

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)用”（如：路徑長度）成正比，那么，找到的第一個(gè)解即為最優(yōu)解，這時(shí)，搜索速度比深度搜索要快些，在求最優(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ù)增長。

下面我們看看怎樣用寬度優(yōu)先搜索來解決八數(shù)碼問題。例如圖2給出廣度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹。搜索樹上的所有結(jié)點(diǎn)都標(biāo)記它們所對應(yīng)的狀態(tài)，每個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示結(jié)點(diǎn)擴(kuò)展的順序。粗線條路徑表明求得的一個(gè)解。從圖中可以看出，擴(kuò)展第２６個(gè)結(jié)點(diǎn)，總共生成４６個(gè)結(jié)點(diǎn)之后，才求得這個(gè)解。此外，直接觀察此圖表明，不存在有更短走步序列的解?！纠?】圖4表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過若干個(gè)城市?，F(xiàn)要找出一條經(jīng)過城市最少的一條路線?！舅惴ǚ治觥靠吹竭@圖很容易想到用鄰接距陣來表示，0表示能走，1表示不能走。如圖。

首先想到的是用隊(duì)列的思想。a數(shù)組是存儲(chǔ)擴(kuò)展結(jié)點(diǎn)的隊(duì)列，a[i].city記錄經(jīng)過的城市,a[i].pre記錄前趨城市，這樣就可以倒推出最短線路。具體過程如下：（1）將城市A入隊(duì)，隊(duì)首為0、隊(duì)尾為1。（2）將隊(duì)首所指的城市所有可直通的城市入隊(duì)（如果這個(gè)城市在隊(duì)列中出現(xiàn)過就不入隊(duì)，可用一個(gè)集合來判斷），將入隊(duì)城市的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=record//記錄定義

city:char;

pre:integer;

end;

varhead,tail,i:integer;

a:array[1..100]ofnode;

s:setof'A'..'H';procedureout(d:integer);//輸出過程

begin

write(a[d].city);repeat

d:=a[d].pre;write('--',a[d].city);

untila[d].pre=0;

writeln;

end;proceduredoit;

begin

head:=0;tail:=1;

a[1].city:=‘A’;

a[1].pre:=0;

s:=[‘A’];

repeat//步驟2

inc(head);//隊(duì)首加一，出隊(duì)

fori:=1to8do//搜索可直通的城市

if（ju[ord(a[head].city)-64,i]=0）and（not（chr（i+64）ins））then//判斷城市是否走過

begin

inc(tail);//隊(duì)尾加一，入隊(duì)

a[tail].city:=chr(64+i);

a[tail].pre:=head;

s:=s+[a[tail].city];

ifa[tail].city='H'thenbeginout[tail];break;end;

end;

untilhead=tail;

end;BEGIN//主程序doit;END.輸出：

H--F--A【例2】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個(gè)數(shù)。如:陣列4100234500067103456050020456006710000000089有4個(gè)細(xì)胞?！舅惴ǚ治觥竣艔奈募凶x入m*n矩陣陣列，將其轉(zhuǎn)換為boolean矩陣存入bz數(shù)組中；

⑵沿bz數(shù)組矩陣從上到下，從左到右，找到遇到的第一個(gè)細(xì)胞；

⑶將細(xì)胞的位置入隊(duì)h，并沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置bz數(shù)組置為FLASE；⑷將h隊(duì)的隊(duì)頭出隊(duì)，沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置bz數(shù)組置為FLASE；

⑸重復(fù)4，直至h隊(duì)空為止，則此時(shí)找出了一個(gè)細(xì)胞；

⑹重復(fù)2，直至矩陣找不到細(xì)胞；

⑺輸出找到的細(xì)胞數(shù)。

programEx8_2;constdx:array[1..4]of-1..1=(-1,0,1,0);

dy:array[1..4]of-1..1=(0,1,0,-1);

varname,s:string;

pic:array[1..50,1..79]ofinteger;

bz:array[1..50,1..79]ofboolean;

m,n,i,j,num:integer;

h:array[1..4000,1..2]ofinteger;

proceduredoit(p,q:integer);

vari,t,w,x,y:integer;

begin

inc(num);bz[p,q]:=false;

t:=1;w:=1;h[1,1]:=p;h[1,2]:=q;//遇到的第一個(gè)細(xì)胞入隊(duì)

repeat

fori:=1to4do//沿細(xì)胞的上下左右四個(gè)方向搜索細(xì)胞

begin

x:=h[t,1]+dx[i];y:=h[t,2]+dy[i];

if(x>0)and(x<=m)and(y>0)and(y<=n)andbz[x,y]

thenbegininc(w);h[w,1]:=x;h[w,2]:=y;bz[x,y]:=false;end;end;//本方向搜索到細(xì)胞就入隊(duì)

inc(t);//隊(duì)頭指針加1untilt>w;//直至隊(duì)空為止

end;begin

fillchar(bz,sizeof(bz),true);num:=0;readln(m,n);

fori:=1tomdo

beginreadln(s);

forj:=1tondo

beginpic[i,j]:=ord(s[j])-ord(‘0’);

ifpic[i,j]=0thenbz[i,j]:=false;

end;

end;

fori:=1tomdoforj:=1tondoifbz[i,j]thendoit(i,j);//在矩陣中尋找細(xì)胞

writeln('NUMBERofcells=',num);readln;end.【例3】最短路徑（1995年高中組第4題）如下圖所示，從入口（1）到出口（17）的可行路線圖中，數(shù)字標(biāo)號表示關(guān)卡。現(xiàn)將上面的路線圖，按記錄結(jié)構(gòu)存儲(chǔ)如下圖6：請?jiān)O(shè)計(jì)一種能從存儲(chǔ)數(shù)據(jù)中求出從入口到出口經(jīng)過最少關(guān)卡路徑的算法?！舅惴ǚ治觥?/p>

該題是一個(gè)路徑搜索問題，根據(jù)圖示，從入口（1）到出口（17）可能有多條途徑，其中最短的路徑只有一條，那么如何找最短路徑呢？根據(jù)題意，用數(shù)組NO存儲(chǔ)各關(guān)卡號，用數(shù)組PRE存儲(chǔ)訪問到某關(guān)卡號的前趨關(guān)卡號。其實(shí)本題是一個(gè)典型的圖的遍歷問題，我們可以采用圖的廣度優(yōu)先遍歷，并利用隊(duì)列的方式存儲(chǔ)頂點(diǎn)之間的聯(lián)系。從入口（1）開始先把它入隊(duì)，然后把（1）的所有關(guān)聯(lián)頂點(diǎn)都入隊(duì)，即訪問一個(gè)頂點(diǎn)，將其后繼頂點(diǎn)入隊(duì)，并存儲(chǔ)它的前趨頂點(diǎn)，……，直到訪問到出口（17）。最后，再從出口的關(guān)卡號（17）開始回訪它的前趨關(guān)卡號，……，直到入口的關(guān)卡號（1），則回訪的搜索路徑便是最短路徑。從列表中可以看出出口關(guān)卡號（17）的被訪問路徑最短的是：（17）←（16）←（19）←（18）←（1）由此，我們得到廣度優(yōu)先遍歷求最短路徑的基本方法如下：假設(shè)用鄰接矩陣存放路線圖（a[I,j]=1表示I與j連通，a[I,j]=0表示I與j不連通）。再設(shè)一個(gè)隊(duì)列和一個(gè)表示拓展到哪個(gè)頂點(diǎn)的指針變量pos。（1）從入口開始，先把（1）入隊(duì)，并且根據(jù)鄰接矩陣，把（1）的后繼頂點(diǎn)全部入隊(duì)，并存儲(chǔ)這些后繼頂點(diǎn)的前趨頂點(diǎn)為（1）；再把pos后移一個(gè)，繼續(xù)拓展它，將其后繼頂點(diǎn)入隊(duì)，并存儲(chǔ)它們的前趨頂點(diǎn)，……，直到拓展到出口（目的地（17））；

注意后繼頂點(diǎn)入隊(duì)前，必須要檢查這個(gè)頂點(diǎn)是否已在隊(duì)列中，如果已經(jīng)在了就不要入隊(duì)了；這一步可稱為圖的遍歷或拓展；（2）從隊(duì)列的最后一個(gè)關(guān)卡號（出口（17））開始，依次回訪它的前驅(qū)頂點(diǎn)，倒推所得到的路徑即為最短路徑。主要是依據(jù)每個(gè)頂點(diǎn)的前趨頂點(diǎn)倒推得到的。實(shí)現(xiàn)如下：

I：=1；

WHILENO[I]<>17DOI:=I+1;REPEATWRITE(‘(‘,NO[I],’)’);WRITE(‘←’);I:=PRE[I];UNTILI=0；【參考程序】留給同學(xué)們完成，文件名ex8_3.pas?！纠?】迷宮問題如下圖所示，給出一個(gè)N*M的迷宮圖和一個(gè)入口、一個(gè)出口。編一個(gè)程序，打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），白色方塊的單元表示可以走（用0表示）。只能往上、下、左、右四個(gè)方向走。如果無路則輸出“noway.”。入口→0-1000000-10000-1000-1-100000-1-1-100-1-100000→出口0000000-1-1【算法分析】只要輸出一條路徑即可，所以是一個(gè)經(jīng)典的回溯算法問題，本例給出了回溯（深搜）程序和廣搜程序。實(shí)現(xiàn)見參考程序?！旧钏褏⒖汲绦颉縫rogramEX8_4_1;constmaxn=50;varmap:array[1..maxn,1..maxn]ofinteger;f:boolean;n,m,i,j,desx,desy,soux,souy,totstep:integer;route:array[1..maxn]ofrecordx,y:integer;end;proceduremove(x,y,step:integer);beginmap[x,y]:=step;//走一步，作標(biāo)記，把步數(shù)記下來

route[step].x:=x;route[step].y:=y;//記路徑

if(x=desx)and(y=desy)thenbeginf:=true;totstep:=step;endelsebeginif(y<>m)and(map[x,y+1]=0)thenmove(x,y+1,step+1);//向右

ifnotfand(x<>n)and(map[x+1,y]=0)thenmove(x+1,y,step+1);//往下

ifnotfand(y<>1)and(map[x,y-1]=0)thenmove(x,y-1,step+1);//往左

ifnotfand(x<>1)and(map[x-1,y]=0)thenmove(x-1,y,step+1);//往上

end;end;BEGINreadln(n,m);//n行m列的迷宮

fori:=1tondo//讀入迷宮，0表示通，-1表示不通

beginforj:=1tomdoread(map[i,j]);readln;end;write('inputtheenter:');readln(soux,souy);//入口

write('inputtheexit:');readln(desx,desy);//出口

f:=false;//f=false表示無解；f=true表示找到了一個(gè)解

move(soux,souy,1);iffthenfori:=1tototstepdo //輸出直迷宮的路徑

write(route[i]:4);elsewriteln('noway.');END.【廣搜參考程序】programEX8_4_2;constmaxn=50;u:array[1..4]ofinteger=(0,1,0,-1);w:array[1..4]ofinteger=(1,0,-1,0);varmap:array[1..maxn,1..maxn]ofinteger;f:boolean;n,m,i,j,desx,desy,soux,souy,head,tail,x,y:integer;route:array[1..maxn]ofrecordx,y,pre:integer;end;procedureprint(d:integer);beginifroute[d].pre<>0thenprint(route[d].pre);write('(',route[d].x,',',route[d].y,')');end;BEGINreadln(n,m);//n行m列的迷宮

fori:=1tondo//讀入迷宮，0表示通，-1表示不通

beginforj:=1tomdoread(map[i,j]);readln;end;write('inputtheenter:');readln(soux,souy);//入口write('inputtheexit:');readln(desx,desy);//出口

head:=0;tail:=1;f:=false;map[soux,souy]:=-1;route[tail].x:=soux;route[tail].y:=souy;route[tail].pre:=0;whilehead<>taildo //隊(duì)列不為空

begininc(head);fori:=1to4do //4個(gè)方向

beginx:=route[head].x+u[i];y:=route[head].y+w[i];if(x>0)and(x<=n)and(y>0)and(y<=m)and(map[x,y]=0) then begin //本方向上可以走

inc(tail);route[tail].x:=x;route[tail].y:=y;route[tail].pre:=head;map[x,y]:=-1;if(x=desx)and(y=desy)then //擴(kuò)展出的結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)

beginf:=true;print(tail);break;end;end;end;iffthenbreak;end;ifnotfthenwriteln('noway!');END.輸入1：輸出1：輸入2：輸出2：85-1-1-1-1-10000-1-1-1-10-1-1000-1-100-1-1-1000-1-1-1-10-1-1000-12184-1-1-1-1-11234-1-1-1-15-1-1076-1-108-1-1-10910-1-1-1-111-1-10012-185-1-1-1-1-10000-1-1-1-10-1-1000-1-100-1-1-1000-1-1-1-1-1-1-1000-12184noway.【上機(jī)練習(xí)】1、編程計(jì)算由“*”號圍成的下列圖形的面積。面積計(jì)算方法是統(tǒng)計(jì)*號所圍成的閉合曲線中水平線和垂直線交點(diǎn)的數(shù)目。如下圖所示，在10*10的二維數(shù)組中，有“*”圍住了15個(gè)點(diǎn)，因此面積為15。00000000000000***0000000*00*0000000*00*000*000*0*00*0*0*00*00*00**0**000*0000*00000*****000000000000【樣例輸入】area.in0000000000000011100000001001000000010010001000101001010100100100110110001000010000011111000000000000【樣例輸出】area.out152、細(xì)胞(cell.pas)【問題描述】

一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求