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

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

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

指針head后移一位，指向待擴展結點；

forI=1tomaxdo//max為產生子結點的規(guī)則數

beginif子結點符合條件thenbegintail指針增1，把新結點存入列尾；

if新結點與原已產生結點重復then刪去該結點（取消入隊，tail減1）

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

2、生成的結點要與前面所有已經產生結點比較，以免出現重復結點，浪費時間，還有可能陷入死循環(huán)。

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

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

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

首先想到的是用隊列的思想。a數組是存儲擴展結點的隊列，a[i].city記錄經過的城市,a[i].pre記錄前趨城市，這樣就可以倒推出最短線路。具體過程如下：（1）將城市A入隊，隊首為0、隊尾為1。（2）將隊首所指的城市所有可直通的城市入隊（如果這個城市在隊列中出現過就不入隊，可用一個集合來判斷），將入隊城市的pre指向隊首的位置。然后將隊首加1，得到新的隊首城市。重復以上步驟，直到搜到城市H時，搜索結束。利用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】一矩形陣列由數字0到9組成,數字1到9代表細胞,細胞的定義為沿細胞數字上下左右還是細胞數字則為同一細胞,求給定矩形陣列的細胞個數。如:陣列4100234500067103456050020456006710000000089有4個細胞。【算法分析】⑴從文件中讀入m*n矩陣陣列，將其轉換為boolean矩陣存入bz數組中；

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

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

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

⑹重復2，直至矩陣找不到細胞；

⑺輸出找到的細胞數。

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）的可行路線圖中，數字標號表示關卡?，F將上面的路線圖，按記錄結構存儲如下圖6：請設計一種能從存儲數據中求出從入口到出口經過最少關卡路徑的算法。【算法分析】

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

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

I：=1；

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

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 //擴展出的結點為目標結點

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.【上機練習】1、編程計算由“*”號圍成的下列圖形的面積。面積計算方法是統(tǒng)計*號所圍成的閉合曲線中水平線和垂直線交點的數目。如下圖所示，在10*10的二維數組中，有“*”圍住了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)【問題描述】

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