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

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

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

elseif新結(jié)點是目標(biāo)結(jié)點then輸出并退出；end;end;until(head>=tail);//隊列為空廣度優(yōu)先搜索注意事項：1、每生成一個子結(jié)點，就要提供指向它們父親結(jié)點的指針。當(dāng)解出現(xiàn)時候，通過逆向跟蹤，找到從根結(jié)點到目標(biāo)結(jié)點的一條路徑。當(dāng)然不要求輸出路徑，就沒必要記父親。

2、生成的結(jié)點要與前面所有已經(jīng)產(chǎn)生結(jié)點比較，以免出現(xiàn)重復(fù)結(jié)點，浪費時間，還有可能陷入死循環(huán)。

3、如果目標(biāo)結(jié)點的深度與“費用”（如：路徑長度）成正比，那么，找到的第一個解即為最優(yōu)解，這時，搜索速度比深度搜索要快些，在求最優(yōu)解時往往采用廣度優(yōu)先搜索；如果結(jié)點的“費用”不與深度成正比時，第一次找到的解不一定是最優(yōu)解。

4、廣度優(yōu)先搜索的效率還有賴于目標(biāo)結(jié)點所在位置情況，如果目標(biāo)結(jié)點深度處于較深層時，需搜索的結(jié)點數(shù)基本上以指數(shù)增長。

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

首先想到的是用隊列的思想。a數(shù)組是存儲擴展結(jié)點的隊列，a[i].city記錄經(jīng)過的城市,a[i].pre記錄前趨城市，這樣就可以倒推出最短線路。具體過程如下：（1）將城市A入隊，隊首為0、隊尾為1。（2）將隊首所指的城市所有可直通的城市入隊（如果這個城市在隊列中出現(xiàn)過就不入隊，可用一個集合來判斷），將入隊城市的pre指向隊首的位置。然后將隊首加1，得到新的隊首城市。重復(fù)以上步驟，直到搜到城市H時，搜索結(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);//隊首加一，出隊

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

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

begin

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

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代表細胞,細胞的定義為沿細胞數(shù)字上下左右還是細胞數(shù)字則為同一細胞,求給定矩形陣列的細胞個數(shù)。如:陣列4100234500067103456050020456006710000000089有4個細胞。【算法分析】⑴從文件中讀入m*n矩陣陣列，將其轉(zhuǎn)換為boolean矩陣存入bz數(shù)組中；

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

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

⑸重復(fù)4，直至h隊空為止，則此時找出了一個細胞；

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

⑺輸出找到的細胞數(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;//遇到的第一個細胞入隊

repeat

fori:=1to4do//沿細胞的上下左右四個方向搜索細胞

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;//本方向搜索到細胞就入隊

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

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);//在矩陣中尋找細胞

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

該題是一個路徑搜索問題，根據(jù)圖示，從入口（1）到出口（17）可能有多條途徑，其中最短的路徑只有一條，那么如何找最短路徑呢？根據(jù)題意，用數(shù)組NO存儲各關(guān)卡號，用數(shù)組PRE存儲訪問到某關(guān)卡號的前趨關(guān)卡號。其實本題是一個典型的圖的遍歷問題，我們可以采用圖的廣度優(yōu)先遍歷，并利用隊列的方式存儲頂點之間的聯(lián)系。從入口（1）開始先把它入隊，然后把（1）的所有關(guān)聯(liá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è)一個隊列和一個表示拓展到哪個頂點的指針變量pos。（1）從入口開始，先把（1）入隊，并且根據(jù)鄰接矩陣，把（1）的后繼頂點全部入隊，并存儲這些后繼頂點的前趨頂點為（1）；再把pos后移一個，繼續(xù)拓展它，將其后繼頂點入隊，并存儲它們的前趨頂點，……，直到拓展到出口（目的地（17））；

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

I：=1；

WHILENO[I]<>17DOI:=I+1;REPEATWRITE(‘(‘,NO[I],’)’);WRITE(‘←’);I:=PRE[I];UNTILI=0；【參考程序】留給同學(xué)們完成，文件名ex8_3.pas。【例4】迷宮問題如下圖所示，給出一個N*M的迷宮圖和一個入口、一個出口。編一個程序，打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），白色方塊的單元表示可以走（用0表示）。只能往上、下、左、右四個方向走。如果無路則輸出“noway.”。入口→0-1000000-10000-1000-1-100000-1-1-100-1-100000→出口0000000-1-1【算法分析】只要輸出一條路徑即可，所以是一個經(jīng)典的回溯算法問題，本例給出了回溯（深搜）程序和廣搜程序。實現(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表示找到了一個解

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 //隊列不為空

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

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 //擴展出的結(jié)點為目標(biāo)結(jié)點

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.【上機練習(xí)】1、編程計算由“*”號圍成的下列圖形的面積。面積計算方法是統(tǒng)計*號所圍成的閉合曲線中水平線和垂直線交點的數(shù)目。如下圖所示，在10*10的二維數(shù)組中，有“*”圍住了15個點，因此面積為15。00000000000000***0000000*00*0000000*00*000*000*0*00*0*0*00*00*00**0**000*0000*00000*****000000000000【樣例輸入】area.in0000000000000011100000001001000000010010001000101001010100100100110110001000010000011111000000000000【樣例輸出】area.out152、細胞(cell.pas)【問題描述】

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