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

廣度寬度優(yōu)先搜索第一頁(yè)，共三十九頁(yè)，2022年，8月28日深度搜索與廣度搜索區(qū)分[深度搜索與廣度搜索]深度搜索與廣度搜索的區(qū)別：深度搜索下一次擴(kuò)展的是本次擴(kuò)展出來(lái)的子節(jié)點(diǎn)中的一個(gè)，而廣度搜索擴(kuò)展的則是本次擴(kuò)展的節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。在具體實(shí)現(xiàn)上為了提高效率,所以采用了不同的數(shù)據(jù)結(jié)構(gòu)。廣度搜索是求解最優(yōu)解的一種較好的方法，而深度搜索多用于只要求解，并且解答樹(shù)中的重復(fù)節(jié)點(diǎn)較多并且重復(fù)較難判斷時(shí)使用，但往往可以用回溯算法代替。第二頁(yè)，共三十九頁(yè)，2022年，8月28日一些基本概念節(jié)點(diǎn)：記錄擴(kuò)展的狀態(tài)?；?邊：記錄擴(kuò)展的路徑。搜索樹(shù)：描述搜索擴(kuò)展的整個(gè)過(guò)程。節(jié)點(diǎn)的耗散值 令C(i,j)為從節(jié)點(diǎn)ni到nj的這段路徑（或者?。┑暮纳⒅?一條路徑的耗散值就等于連接這條路徑各節(jié)點(diǎn)間所有弧的耗散值總和?？梢杂眠f歸公式描述如下：

C(ni,t)=C(ni,nj)+C(nj,t)4搜索樹(shù)根節(jié)點(diǎn)葉子節(jié)點(diǎn)4,5,6,7,88123567第三頁(yè)，共三十九頁(yè)，2022年，8月28日廣度優(yōu)先搜索的過(guò)程

廣度優(yōu)先搜索算法（又稱(chēng)寬度優(yōu)先搜索）是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹(shù)算法都采用了和寬度優(yōu)先搜索類(lèi)似的思想。廣度優(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)為止。即⒈從圖中的某一頂點(diǎn)V0開(kāi)始，先訪問(wèn)V0；⒉訪問(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ì)，所以稱(chēng)之為廣度優(yōu)先搜索。第四頁(yè)，共三十九頁(yè)，2022年，8月28日廣度搜索策略綜合數(shù)據(jù)庫(kù)（變量設(shè)置）

與問(wèn)題相關(guān)的所有數(shù)據(jù)元素構(gòu)成的集合，用來(lái)表述問(wèn)題狀態(tài)或有關(guān)事實(shí)。產(chǎn)生式規(guī)則 構(gòu)建了綜合數(shù)據(jù)庫(kù)以后，還需要研究問(wèn)題的移動(dòng)規(guī)則，稱(chēng)為產(chǎn)生式規(guī)則。搜索策略 搜索策略的實(shí)質(zhì)是確定如何選取規(guī)則的方式。有兩種基本方式：一種是不考慮給定問(wèn)題所具有的特定知識(shí)，系統(tǒng)根據(jù)事先確定好某種固定順序，依次調(diào)用規(guī)則或隨機(jī)調(diào)用規(guī)則，這實(shí)際上是盲目搜索的方法。另一種是考慮問(wèn)題領(lǐng)域可應(yīng)用的知識(shí)，動(dòng)態(tài)地確定規(guī)則的排列次序，優(yōu)先調(diào)用較合適的規(guī)則使用，這就是通常所說(shuō)的啟發(fā)式搜索策略。第五頁(yè)，共三十九頁(yè)，2022年，8月28日廣度優(yōu)先搜索算法描述：Programbfs；初始化，初始狀態(tài)存入隊(duì)列；隊(duì)列首指針head:=0;尾指針tail:=1；repeat

指針head后移一位，指向待擴(kuò)展結(jié)點(diǎn)；

fori:=1tomaxdobegin//max為產(chǎn)生子結(jié)點(diǎn)的規(guī)則數(shù)if子結(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è)，共三十九頁(yè)，2022年，8月28日廣度優(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í)，搜索速度比深度搜索要快些，在求最優(yōu)解時(shí)往往采用廣度優(yōu)先搜索；如果結(jié)點(diǎn)的“費(fèi)用”不與深度成正比時(shí)，第一次找到的解不一定是最優(yōu)解。

4、廣度優(yōu)先搜索的效率還有賴(lài)于目標(biāo)結(jié)點(diǎn)所在位置情況，如果目標(biāo)結(jié)點(diǎn)深度處于較深層時(shí)，需搜索的結(jié)點(diǎn)數(shù)基本上以指數(shù)增長(zhǎng)。第七頁(yè)，共三十九頁(yè)，2022年，8月28日八數(shù)碼問(wèn)題

在3*3組成的九宮格棋盤(pán)上，擺有八個(gè)將牌，每一個(gè)將牌都刻有1—8中的某一個(gè)數(shù)碼。棋盤(pán)中留有一個(gè)空格，允許其周?chē)哪骋粋€(gè)將牌向空格中移動(dòng)，如圖1所示。這樣通過(guò)移動(dòng)將牌就可以不斷改變的布局結(jié)構(gòu)，給出一個(gè)初始布局（稱(chēng)初始狀態(tài)）和一個(gè)目標(biāo)布局（稱(chēng)目標(biāo)狀態(tài)），問(wèn)如何移動(dòng)將牌，才能實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)換。

下面我們看看怎樣用寬度優(yōu)先搜索來(lái)解決八數(shù)碼問(wèn)題。圖2給出廣度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹(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è)解。此外，直接觀察此圖表明，不存在有更短走步序列的解。第八頁(yè)，共三十九頁(yè)，2022年，8月28日八數(shù)碼問(wèn)題擴(kuò)展搜索樹(shù)

第九頁(yè)，共三十九頁(yè)，2022年，8月28日綜合數(shù)據(jù)庫(kù)（變量設(shè)置）{Pxy}，其中1<=x,y<=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等

用Pascal語(yǔ)言描述如下：typet8no=array[1..3,1..3]oflongint;{棋盤(pán)狀態(tài)}tList=record{描述一個(gè)節(jié)點(diǎn)}Father:longint;

{父指針}dep:longint;

{深度}x,y:longint; {空格的位置}state:t8no;

end;const

Max=10000;vars,t:t8no;{s為初始狀態(tài)，t為目標(biāo)狀態(tài)}List:array[0..max]oftList;{綜合數(shù)據(jù)庫(kù)}第十頁(yè)，共三十九頁(yè)，2022年，8月28日產(chǎn)生式規(guī)則（關(guān)系）if條件then規(guī)則；設(shè)Pxy表示將牌第x行第y列的數(shù)碼，m,n表示數(shù)碼空格所在的行列值，記Pm,n=0,則可以得到如下四條規(guī)則：

①ifn-1>=1thenbeginPm,n:=Pm,n-1-

;Pm,n-1-

-:=0end;②ifm-1>=1thenbeginPm,n:=Pm-1,n;Pm-1,n:=0end;③ifn+1<=3thenbeginPm,n:=Pm,n+1;Pm,n+1:=0end;④ifm+1<=3thenbeginPm,n:=Pm+1-,n;Pm+1-,n:=0end;ConstDir:array[1..4,1..2]oflongint{對(duì)應(yīng)四種產(chǎn)生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));第十一頁(yè)，共三十九頁(yè)，2022年，8月28日控制策略

PROCEDUREProduction-System；DATA初始化數(shù)據(jù)庫(kù)Repeat

在規(guī)則集中選擇某一條可作用于DATA的規(guī)則R

DATAR作用于DATA后得到的結(jié)果

UntilDATA滿(mǎn)足結(jié)束條件第十二頁(yè)，共三十九頁(yè)，2022年，8月28日八數(shù)碼問(wèn)題寬度優(yōu)先算法框架List[1]=source;closed:=0;open:=1;{加入初始節(jié)點(diǎn),List為擴(kuò)展節(jié)點(diǎn)的表}Repeatclosed:=closed+1;n:=List[closed];{取出closed對(duì)應(yīng)的節(jié)點(diǎn)}Forx:=1to4dobeginnew:=move(n,4);{對(duì)n節(jié)點(diǎn)使用第x條規(guī)則，得到new}ifnot_appear(new,List)thenbegin{如果new沒(méi)有在List中出現(xiàn)}open:=open+1;List[open]:=new;{加入新節(jié)點(diǎn)到open}List[open].Father:=closed;{修改指針}ifList[open]=GoalthenGetOut;end;enduntilclosed<open;第十三頁(yè)，共三十九頁(yè)，2022年，8月28日八數(shù)碼參考程序（寬度優(yōu)先）program8no_bfs;{八數(shù)碼的寬度優(yōu)先搜索算法}Constdir:array[1..4,1..2]oflongint

{四種移動(dòng)方向，對(duì)應(yīng)產(chǎn)生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));n=10000;TypeT8no=array[1..3,1..3]oflongint;TList=recordFather:longint;

{父指針}dep:longint;

{深度}X0,Y0:longint; {0的位置}State:T8no;

{棋盤(pán)狀態(tài)}end;VarSource,Target:T8no;List:array[0..10000]ofTList;{綜合數(shù)據(jù)庫(kù)}Closed,open,Best:integer{Best表示最優(yōu)移動(dòng)次數(shù)}Answer:integer;{記錄解}Found:Boolean;{解標(biāo)志}第十四頁(yè)，共三十九頁(yè)，2022年，8月28日procedureGetInfo;{讀入初始和目標(biāo)節(jié)點(diǎn)}vari,j:integer;beginfori:=1to3doforj:=1to3doread(Source[i,j]);fori:=1to3doforj:=1to3doread(Target[i,j]);end;procedureInitialize;{初始化}varx,y:integer;beginFound:=false;Closed:=0;open:=1;withList[1]dobeginState:=Source;dep:=0;Father:=0;Forx:=1to3doFory:=1to3doifState[x,y]=0thenBeginx0:=x;y0:=y;End;end;end;第十五頁(yè)，共三十九頁(yè)，2022年，8月28日f(shuō)unctionnot_Appear(new:tList):boolean;{判斷new是否在List中出現(xiàn)}vari:integer;beginnot_Appear:=false;fori:=1toopendoifSame(new.State,List[i].State)thenexit;not_Appear:=true;end;procedureMove(n:tList;d:integer;varok:boolean;varnew:tList);{將第d條規(guī)則作用于n得到new,OK是new是否可行的標(biāo)志}varx,y:integer;beginX:=n.x0+Dir[d,1];Y:=n.y0+Dir[d,2];{判斷new的可行性}ifnot((X>0)and(X<4)and(Y>0)and(Y<4))thenbeginok:=false;exitend;OK:=true;FunctionSame(A,B:T8no):Boolean;{判斷A,B狀態(tài)是否相等}Vari,j:integer;BeginSame:=false;Fori:=1to3doforj:=1to3doifA[i,j]<>B[i,j]thenexit;Same:=true;End;第十六頁(yè)，共三十九頁(yè)，2022年，8月28日new.State:=n.State;{new=Expand(n,d)}new.State[X,Y]:=0;new.State[n.x0,n.y0]:=n.State[X,Y];new.X0:=X;new.Y0:=Y;end;procedureAdd(new:tList);{插入節(jié)點(diǎn)new}beginifnot_Appear(new)thenBegin{如果new沒(méi)有在List出現(xiàn)}Inc(open);{new加入open表}List[open]:=new;end;end;第十七頁(yè)，共三十九頁(yè)，2022年，8月28日procedureExpand(Index:integer;varn:tList);{擴(kuò)展n的子節(jié)點(diǎn)}vari:integer;new:tList;OK:boolean;BeginifSame(n.State,Target)thenbegin{如果找到解}Found:=true;Best:=n.Dep;Answer:=Index;Exit;end;Fori:=1to4dobegin{依次使用４條規(guī)則}Move(n,i,OK,new);ifnotokthencontinue;new.Father:=Index;new.Dep:=n.dep+1;Add(new);end;end;

第十八頁(yè)，共三十九頁(yè)，2022年，8月28日procedureGetOutInfo;{輸出}procedureOutlook(Index:integer);{遞歸輸出每一個(gè)解}vari,j:integer;beginifIndex=0thenexit;Outlook(List[Index].Father);withList[Index]dofori:=1to3dobeginforj:=1to3dowrite(State[i,j],'');writeln;end;writeln;end;beginWriteln('Total=',Best);Outlook(Answer);end;第十九頁(yè)，共三十九頁(yè)，2022年，8月28日procedureMain;{搜索主過(guò)程}beginRepeatInc(Closed);Expand(Closed,List[Closed]);{擴(kuò)展Closed}Until(Closed>=open)orFound;ifFoundthenGetOutInfo{存在解}elseWriteln('noanswer');{無(wú)解}end;beginAssign(Input,'input.txt');ReSet(Input);Assign(Output,'Output.txt');ReWrite(Output);GetInfo;Initialize;Main;Close(Input);Close(Output);End.第二十頁(yè)，共三十九頁(yè)，2022年，8月28日【例1】圖4表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過(guò)若干個(gè)城市?，F(xiàn)要找出一條經(jīng)過(guò)城市最少的一條路線。第二十一頁(yè)，共三十九頁(yè)，2022年，8月28日【算法分析】看到這圖很容易想到用鄰接距陣來(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ì)城市的pre指向隊(duì)首的位置。然后將隊(duì)首加1，得到新的隊(duì)首城市。重復(fù)以上步驟，直到搜到城市H時(shí)，搜索結(jié)束。利用pre可倒推出最少城市線路。第二十二頁(yè)，共三十九頁(yè)，2022年，8月28日【參考程序】ProgramEx8_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);//輸出過(guò)程

begin

write(a[d].city);repeat

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

untila[d].pre=0;

writeln;

end;第二十三頁(yè)，共三十九頁(yè)，2022年，8月28日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））thenbegin//判斷城市是否走過(guò)

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第二十四頁(yè)，共三十九頁(yè)，2022年，8月28日【例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ù)。

第二十五頁(yè)，共三十九頁(yè)，2022年，8月28日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;第二十六頁(yè)，共三十九頁(yè)，2022年，8月28日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.第二十七頁(yè)，共三十九頁(yè)，2022年，8月28日【例3】最短路徑（1995年高中組第4題）如下圖所示，從入口（1）到出口（17）的可行路線圖中，數(shù)字標(biāo)號(hào)表示關(guān)卡?，F(xiàn)將上面的路線圖，按記錄結(jié)構(gòu)存儲(chǔ)如下圖6：請(qǐng)?jiān)O(shè)計(jì)一種能從存儲(chǔ)數(shù)據(jù)中求出從入口到出口經(jīng)過(guò)最少關(guān)卡路徑的算法。第二十八頁(yè)，共三十九頁(yè)，2022年，8月28日【算法分析】

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

第二十九頁(yè)，共三十九頁(yè)，2022年，8月28日

注意后繼頂點(diǎn)入隊(duì)前，必須要檢查這個(gè)頂點(diǎn)是否已在隊(duì)列中，如果已經(jīng)在了就不要入隊(duì)了；這一步可稱(chēng)為圖的遍歷或拓展；（2）從隊(duì)列的最后一個(gè)關(guān)卡號(hào)（出口（17））開(kāi)始，依次回訪它的前驅(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。第三十頁(yè)，共三十九頁(yè)，2022年，8月28日【例4】迷宮問(wèn)題如下圖所示，給出一個(gè)N*M的迷宮圖和一個(gè)入口、一個(gè)出口。編一個(gè)程序，打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），白色方塊的單元表示可以走（用0表示）。只能往上、下、左、右四個(gè)方向走。如果無(wú)路則輸出“noway.”。入口→0-1000000-10000-1000-1-100000-1-1-100-1-100000→出口0000000-1-1【算法分析】只要輸出一條路徑即可，所以是一個(gè)經(jīng)典的回溯算法問(wèn)題，本例給出了回溯（深搜）程序和廣搜程序。實(shí)現(xiàn)見(jiàn)參考程序。第三十一頁(yè)，共三十九頁(yè)，2022年，8月28日【深搜參考程序】programEX8_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ù)記下來(lái)

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;第三十二頁(yè)，共三十九頁(yè)，2022年，8月28日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表示無(wú)解；f=true表示找到了一個(gè)解

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

write(route[i]:4);elsewriteln('noway.');END.第三十三頁(yè)，共三十九頁(yè)，2022年，8月28日【廣搜參考程序】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);//入口第三十四頁(yè)，共三十九頁(yè)，2022年，8月28日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.第三十五頁(yè)，共三十九頁(yè)，2022年，8月28日輸入1：輸出1：輸入2