寬度優(yōu)先搜索

寬度優(yōu)先搜索應(yīng)用實(shí)例長(zhǎng)沙市雅禮中學(xué)朱全民知識(shí)重點(diǎn)寬度優(yōu)先算法的基本原理與構(gòu)造方法寬度優(yōu)先算法的實(shí)現(xiàn)狀態(tài)空間的描述寬度優(yōu)先算法的應(yīng)用寬度有先算法的優(yōu)化方法寬度優(yōu)先搜索框架PROCEDUREBFS-SEARCH;1.

G:=G0;{初始化圖}2.

closed:=(Source);{隊(duì)首指針指向初始結(jié)點(diǎn)}3.

open:=(Source);{隊(duì)尾指針指向空}4.

Repeat5.

n:=GET(closed){取出closed指向的結(jié)點(diǎn),記為n}6.

ifn=GoalthenExit(Success);

7.

whilen能擴(kuò)展do[8m:=Expand(n);{擴(kuò)展取出的結(jié)點(diǎn)}9.inc(open);Add(m,open);{隊(duì)尾指針后移,并插入隊(duì)列}10.

Add(m,G);{構(gòu)圖}]11.

inc(closed);{隊(duì)首指針后移}12.

Untilclosed=open;

13.Exit(Fail);八數(shù)碼問(wèn)題

在3*3組成的九宮格棋盤(pán)上，擺有八個(gè)將牌，每一個(gè)將牌都刻有1—8中的某一個(gè)數(shù)碼。棋盤(pán)中留有一個(gè)空格，允許其周?chē)哪骋粋€(gè)將牌向空格中移動(dòng)，如右圖所示。這樣通過(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)換。狀態(tài)空間描述{Pxy}，其中1<=x,y<=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等

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

{父指針}dep:byte;

{深度}x,y:byte; {空格的位置}state:T8no;

end;constMax=10000;vars,t:T8no;{s為初始狀態(tài)，t為目標(biāo)狀態(tài)}List:array[0..max]ofTList;{所有結(jié)點(diǎn)}擴(kuò)展規(guī)則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]ofinteger{對(duì)應(yīng)四種產(chǎn)生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));八數(shù)碼問(wèn)題寬度優(yōu)先擴(kuò)展過(guò)程

八數(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:=1to4do[new:=Move(n,4);{對(duì)n節(jié)點(diǎn)使用第x條規(guī)則，得到new}ifnot_Appear(new,List)then[{如果new沒(méi)有在List中出現(xiàn)}open:=open+1;List[open]:=new;{加入新節(jié)點(diǎn)到open}List[open].Father:=closed;{修改指針}ifList[open]=GoalthenGetOut;];]Untilclosed=open;program8no_bfs;{八數(shù)碼的寬度優(yōu)先搜索算法}ConstDir:array[1..4,1..2]ofinteger

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

{父指針}dep:byte;

{深度}X0,Y0:byte; {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)志}procedureGetInfo;{讀入初始和目標(biāo)節(jié)點(diǎn)}vari,j:integer;

procedureInitialize;{初始化}varx,y:integer;beginfori:=1to3doforj:=1to3doread(Source[i,j]);fori:=1to3doforj:=1to3doread(Target[i,j]);Found:=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;

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;functionnot_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;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;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];ifnot((X>0)and(X<4)and(Y>0)and(Y<4))thenbeginok:=false;exitend;ok:=true;new.State:=n.State;new.State[X,Y]:=0;new.State[n.x0,n.y0]:=n.State[X,Y];new.X0:=X;new.Y0:=Y;end;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;

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;

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.思考題1:神經(jīng)網(wǎng)絡(luò)

在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點(diǎn)稱(chēng)為神經(jīng)元，而且兩個(gè)神經(jīng)元之間至多有一條邊相連，下圖是一個(gè)神經(jīng)元的例子：圖中，X1—X3是信息輸入渠道，Y1－Y2是信息輸出渠道，C1表示神經(jīng)元目前的狀態(tài)，Ui是閾值，可視為神經(jīng)元的一個(gè)內(nèi)在參數(shù)。神經(jīng)元按一定的順序排列，構(gòu)成整個(gè)神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無(wú)分為幾層；稱(chēng)為輸入層、輸出層，和若干個(gè)中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。蘭蘭規(guī)定，Ci服從公式(1)（其中n是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目）公式中的Wji（可能為負(fù)值）表示連接j號(hào)神經(jīng)元和i號(hào)神經(jīng)元的邊的權(quán)值。當(dāng)Ci大于0時(shí)，該神經(jīng)元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時(shí)，下一秒它會(huì)向其他神經(jīng)元傳送信號(hào)，信號(hào)的強(qiáng)度為Ci。如此．在輸入層神經(jīng)元被激發(fā)之后，整個(gè)網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿?dòng)下進(jìn)行運(yùn)作。現(xiàn)在，給定一個(gè)神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)Ci，要求你的程序運(yùn)算出最后網(wǎng)絡(luò)輸出層的狀態(tài)。

【輸入格式】

第一行是兩個(gè)整數(shù)n（1≤n≤20）和p。接下來(lái)n行，每行兩個(gè)整數(shù)，第i＋1行是神經(jīng)元i最初狀態(tài)和其閾值（Ui），非輸入層的神經(jīng)元開(kāi)始時(shí)狀態(tài)必然為0。再下面P行，每行由兩個(gè)整數(shù)i，j及一個(gè)整數(shù)Wij，表示連接神經(jīng)元i、j的邊權(quán)值為Wij【輸出格式】

輸出包含若干行，每行有兩個(gè)整數(shù)，分別對(duì)應(yīng)一個(gè)神經(jīng)元的編號(hào)，及其最后的狀態(tài)，兩個(gè)整數(shù)間以空格分隔。僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號(hào)由小到大順序輸出！若輸出層的神經(jīng)元最后狀態(tài)均為0，則輸出NULL。分析

理解問(wèn)題的第一步就是認(rèn)真“讀題”。那么我們先來(lái)看一看這個(gè)題目涉及的問(wèn)題。研究一下題目中所給的圖的一些性質(zhì)，可以發(fā)現(xiàn)如下特點(diǎn)：1．圖中所有的節(jié)點(diǎn)都有一個(gè)確定的等級(jí)，我們記作Level(i)2．圖中所有的邊都是有向的，并且從Level值為i-1的節(jié)點(diǎn)指向Level值為i的節(jié)點(diǎn)我們不妨將其抽象為“階段圖”。更一般地，我們可以發(fā)現(xiàn)所有的階段圖都是有向無(wú)環(huán)的，這樣我們可以通過(guò)拓?fù)渑判騺?lái)得到期望的處理節(jié)點(diǎn)的順序?？尚兴惴?/p>

由于階段圖的性質(zhì)使得該圖的所有邊所連接節(jié)點(diǎn)的等級(jí)都是相鄰的，因此就可以設(shè)計(jì)出一個(gè)基于寬度優(yōu)先搜索（即BFS）的算法：1．初始時(shí)將所有輸入層的節(jié)點(diǎn)放入隊(duì)列；2．取出隊(duì)列中的一個(gè)元素，不重復(fù)地?cái)U(kuò)展并處理該節(jié)點(diǎn)所發(fā)出的邊的目標(biāo)節(jié)點(diǎn)；3．如果隊(duì)列非空，則轉(zhuǎn)向2；4．輸出輸出層中所有滿(mǎn)足條件的節(jié)點(diǎn)。但是由于本題在問(wèn)題描述中并沒(méi)有明確的給出判斷一個(gè)節(jié)點(diǎn)是否是輸入節(jié)點(diǎn)，因此需要在算法進(jìn)行的過(guò)程當(dāng)中額外地考慮一些邊界情況的數(shù)據(jù)（這個(gè)過(guò)程即便是真實(shí)數(shù)據(jù)沒(méi)有這樣出也是要有的），下面給出的更一般的算法可能會(huì)更好的跳過(guò)這些邊界情況。1．對(duì)原圖中所有的節(jié)點(diǎn)進(jìn)行一次拓?fù)渑判颍?．按照拓?fù)漤樞蛱幚砻恳粋€(gè)節(jié)點(diǎn)；3．輸出輸出層中所有滿(mǎn)足條件的節(jié)點(diǎn)。思考題2:聰明的打字員阿蘭是某機(jī)密部門(mén)的打字員，她現(xiàn)在接到一個(gè)任務(wù)：需要在一天之內(nèi)輸入幾百個(gè)長(zhǎng)度固定為6的密碼。當(dāng)然，她希望輸入的過(guò)程中敲擊鍵盤(pán)的總次數(shù)越少越好。不幸的是，出于保密的需要，該部門(mén)用于輸入密碼的鍵盤(pán)是特殊設(shè)計(jì)的，鍵盤(pán)上沒(méi)有數(shù)字鍵，而只有以下六個(gè)鍵：Swap0,Swap1,Up,Down,Left,Right，為了說(shuō)明這6個(gè)鍵的作用，我們先定義錄入?yún)^(qū)的6個(gè)位置的編號(hào)，從左至右依次為1，2，3，4，5，6。下面列出每個(gè)鍵的作用：Swap0：按Swap0，光標(biāo)位置不變，將光標(biāo)所在位置的數(shù)字與錄入?yún)^(qū)的1號(hào)位置的數(shù)字（左起第一個(gè)數(shù)字）交換。如果光標(biāo)已經(jīng)處在錄入?yún)^(qū)的1號(hào)位置，則按Swap0鍵之后，錄入?yún)^(qū)的數(shù)字不變；Swap1：按Swap1，光標(biāo)位置不變，將光標(biāo)所在位置的數(shù)字與錄入?yún)^(qū)的6號(hào)位置的數(shù)字（左起第六個(gè)數(shù)字）交換。如果光標(biāo)已經(jīng)處在錄入?yún)^(qū)的6號(hào)位置，則按Swap1鍵之后，錄入?yún)^(qū)的數(shù)字不變；Up：按Up，光標(biāo)位置不變，將光標(biāo)所在位置的數(shù)字加1（除非該數(shù)字是9）。例如，如果光標(biāo)所在位置的數(shù)字為2，按Up之后，該處的數(shù)字變?yōu)?；如果該處數(shù)字為9，則按Up之后，數(shù)字不變，光標(biāo)位置也不變；Down：按Down，光標(biāo)位置不變，將光標(biāo)所在位置的數(shù)字減1（除非該數(shù)字是0），如果該處數(shù)字為0，則按Down之后，數(shù)字不變，光標(biāo)位置也不變；Left：按Left，光標(biāo)左移一個(gè)位置，如果光標(biāo)已經(jīng)在錄入?yún)^(qū)的1號(hào)位置（左起第一個(gè)位置）上，則光標(biāo)不動(dòng)；Right：按Right，光標(biāo)右移一個(gè)位置，如果光標(biāo)已經(jīng)在錄入?yún)^(qū)的6號(hào)位置（左起第六個(gè)位置）上，則光標(biāo)不動(dòng)。當(dāng)然，為了使這樣的鍵盤(pán)發(fā)揮作用，每次錄入密碼之前，錄入?yún)^(qū)總會(huì)隨機(jī)出現(xiàn)一個(gè)長(zhǎng)度為6的初始密碼，而且光標(biāo)固定出現(xiàn)在1號(hào)位置上。當(dāng)巧妙地使用上述六個(gè)特殊鍵之后，可以得到目標(biāo)密碼，這時(shí)光標(biāo)允許停在任何一個(gè)位置?，F(xiàn)在，阿蘭需要你的幫助，編寫(xiě)一個(gè)程序，求出錄入一個(gè)密碼需要的最少的擊鍵次數(shù)。擴(kuò)展規(guī)則設(shè)當(dāng)前狀態(tài)為(S,index)，下一個(gè)狀態(tài)為(S’,index’)①Swap0：ifindex<>1then[S’:=S;S’[1]:=S[index];S’[index]:=S[1];Index’:=index;]②Swap1：ifindex<>6then[S’:=S;S’[6]:=S[index];S’[index]:=S[6];Index’:=index;]③Up：ifS[index]<>9then[S’:=S;S’[index]:=S’[index]+1;Index’:=index;]④Down：ifS[index]<>0then[S’:=S;S’[index]:=S’[index]-1;Index’:=index;]⑤Left：ifindex<>0then[S’:=S;Index’:=index-1;]⑥Right：ifindex<>6then[S’:=S;Index’:=index+1;]數(shù)據(jù)結(jié)構(gòu)的處理

如果我們用（S,index）表示問(wèn)題中的一個(gè)狀態(tài)，S為密碼，index表示光標(biāo)位置。那么，（Source，1）為問(wèn)題的初始狀態(tài)，（Target，pos）為問(wèn)題的目標(biāo)狀態(tài)。其中pos任意。那么綜合數(shù)據(jù)庫(kù)中可能存在的節(jié)點(diǎn)數(shù)為：6*106。

constmaxl=6000000;typestatetype=array[1..6]ofshortint;Nodetype=recordstate:statetype;{密碼}point,step:shortint;{光標(biāo)位置，按鍵次數(shù)}end;varq:array[0..maxl]ofNodetype;

{隊(duì)列}app:array[1..6,0..9,0..9,0..9,0..9,0..9,0..9]ofboolean;{判重?cái)?shù)組}final:statetype;{目標(biāo)狀態(tài)}算法選擇closed:=0;open:=1;q[1].point:=1;fillchar(app,sizeof(app),false);whiletruedobeginclosed:=closedmodmaxl+1;withq[closed]dobeginifcomparebyte(state,final,6)=0then打印輸出；{如果是目標(biāo)的話(huà)}

調(diào)用6條規(guī)則擴(kuò)展出state新節(jié)點(diǎn)；

ifnotapp[point,state[1],state[2],state[3],state[4],state[5],state[6]]{判重}thenbeginopen:=openmodmaxl+1;q[open].state:=state;q[open].step:=step+1;q[open].point:=point;app[point,state[1],state[2],state[3],state[4],state[5],state[6]]:=true;end;思考題3：街道賽跑下圖給出了一個(gè)沿街道賽跑的路線(xiàn)。圖中有許多點(diǎn)，給以標(biāo)號(hào)0，1，．．．N(此圖中N=9)，點(diǎn)之間可以用含箭頭的線(xiàn)相連。標(biāo)號(hào)為0的點(diǎn)是起點(diǎn)；標(biāo)號(hào)為N的點(diǎn)為終點(diǎn)。含箭頭的線(xiàn)表示單向通行的街道。運(yùn)動(dòng)員沿箭頭所指方向從一個(gè)點(diǎn)跑向另一個(gè)點(diǎn)；在每一個(gè)點(diǎn)上，運(yùn)動(dòng)員可以選擇任何一個(gè)箭頭(向外的)繼續(xù)向前跑。一個(gè)完整路線(xiàn)具有如下特點(diǎn)：

1．路線(xiàn)中每一點(diǎn)都可從出發(fā)點(diǎn)到達(dá)；

2．路線(xiàn)中每一點(diǎn)都可到達(dá)終點(diǎn)；

3．終點(diǎn)處沒(méi)有向外的箭頭。運(yùn)動(dòng)員要到達(dá)終點(diǎn)，但不要求路線(xiàn)（圖）中的每一點(diǎn)都經(jīng)過(guò)。但是路線(xiàn)(圖)中的某些點(diǎn)是必經(jīng)之點(diǎn)。上圖的例子中，必經(jīng)之點(diǎn)是：0，3，6，9。任務(wù)A:題目給出一個(gè)完整路線(xiàn)（圖），請(qǐng)編程找出所有必經(jīng)之點(diǎn)。請(qǐng)注意，輸出必經(jīng)之點(diǎn)時(shí)，應(yīng)不包括起點(diǎn)和終點(diǎn)。任務(wù)B:假定賽跑必須在相鄰的2天來(lái)舉行。因此，要把原來(lái)給定的完整路線(xiàn)（圖）分成兩個(gè)子路線(xiàn)（圖）。第1天從點(diǎn)0出發(fā)，結(jié)束于“分裂點(diǎn)”。第2天從“分裂點(diǎn)”出發(fā)，結(jié)束于點(diǎn)N。題目給出一個(gè)完整路線(xiàn)（圖）C，請(qǐng)編程輸出所有可能的“分裂點(diǎn)”（任務(wù)B）?！胺至腰c(diǎn)”S一定不是起點(diǎn)或終點(diǎn)。C可被S分成兩個(gè)完整的子路線(xiàn)：這兩個(gè)子路線(xiàn)沒(méi)有公共的箭頭線(xiàn)，并且S是這兩個(gè)子路線(xiàn)的唯一公共點(diǎn)。在上的例子中，僅點(diǎn)3是“分裂點(diǎn)”。輸入數(shù)據(jù)： 輸入數(shù)據(jù)描述一個(gè)完整路線(xiàn)（最多50個(gè)點(diǎn)，最多100個(gè)箭頭），共n＋1行。前面n行描述箭頭的終點(diǎn)，其中第i行中的每一個(gè)數(shù)字表示從點(diǎn)i（1≤i≤n）出發(fā)的每一個(gè)箭頭的終點(diǎn)，以－2作為該行的結(jié)束。最后一行（第n+1行）中有一個(gè)數(shù)字－1，表示輸入結(jié)束。輸出數(shù)據(jù)： 輸出兩行數(shù)據(jù)，第1行表示必經(jīng)點(diǎn)（子任務(wù)A）──首先是必經(jīng)點(diǎn)的總數(shù)，其后是必經(jīng)點(diǎn)的標(biāo)號(hào)，標(biāo)號(hào)的順序無(wú)關(guān)緊要。第2行表示“分裂點(diǎn)”：首先是分裂點(diǎn)的總數(shù)，其后是分裂點(diǎn)的標(biāo)號(hào)，標(biāo)號(hào)出現(xiàn)的先后順序無(wú)關(guān)緊要（子任務(wù)B）。分析必經(jīng)點(diǎn):

是指運(yùn)動(dòng)員從起點(diǎn)0出發(fā)，沿箭頭方向跑，無(wú)論走哪條路線(xiàn)，都經(jīng)由該點(diǎn)到達(dá)終點(diǎn)N。所有這些點(diǎn)組成必經(jīng)點(diǎn)的集合。反之，在完整路線(xiàn)中去除必經(jīng)點(diǎn)