寬度優(yōu)先搜索

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

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

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

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

Repeat5.

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

ifn=GoalthenExit(Success);

7.

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

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

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

Untilclosed=open;

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

在3*3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有1—8中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格中移動，如右圖所示。這樣通過移動將牌就可以不斷改變的布局結(jié)構(gòu)，給出一個初始布局（稱初始狀態(tài)）和一個目標(biāo)布局（稱目標(biāo)狀態(tài)），問如何移動將牌，才能實現(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語言描述如下：typeT8no=array[1..3,1..3]ofinteger;{棋盤狀態(tài)}TList=record{描述一個節(jié)點}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é)點}擴展規(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{對應(yīng)四種產(chǎn)生式規(guī)則}=((1,0),(-1,0),(0,1),(0,-1));八數(shù)碼問題寬度優(yōu)先擴展過程

八數(shù)碼問題寬度優(yōu)先算法框架List[1]=source;closed:=0;open:=1;{加入初始節(jié)點,List為擴展節(jié)點的表}Repeatclosed:=closed+1;n:=List[closed];{取出closed對應(yīng)的節(jié)點}Forx:=1to4do[new:=Move(n,x);{對n節(jié)點使用第x條規(guī)則，得到new}ifnot_Appear(new,List)then[{如果new沒有在List中出現(xiàn)}open:=open+1;List[open]:=new;{加入新節(jié)點到open}List[open].Father:=closed;{修改指針}ifList[open]=GoalthenGetOut;];]Untilclosed=open;program8no_bfs;{八數(shù)碼的寬度優(yōu)先搜索算法}ConstDir:array[1..4,1..2]ofinteger{四種移動方向，對應(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; {棋盤狀態(tài)}end;VarSource,Target:T8no;List:array[0..10000]ofTList;{綜合數(shù)據(jù)庫}Closed,open,Best:integer{Best表示最優(yōu)移動次數(shù)}Answer:integer;{記錄解}Found:Boolean;{解標(biāo)志}procedureGetInfo;{讀入初始和目標(biāo)節(jié)點}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é)點new}beginifnot_Appear(new)thenBegin{如果new沒有在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);{擴展n的子節(jié)點}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);{遞歸輸出每一個解}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;{搜索主過程}beginRepeatInc(Closed);Expand(Closed,List[Closed]);{擴展Closed}Until(Closed>=open)orFound;ifFoundthenGetOutInfo{存在解}elseWriteln('noanswer');{無解}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é)點稱為神經(jīng)元，而且兩個神經(jīng)元之間至多有一條邊相連，下圖是一個神經(jīng)元的例子：圖中，X1—X3是信息輸入渠道，Y1－Y2是信息輸出渠道，C1表示神經(jīng)元目前的狀態(tài)，Ui是閾值，可視為神經(jīng)元的一個內(nèi)在參數(shù)。神經(jīng)元按一定的順序排列，構(gòu)成整個神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無分為幾層；稱為輸入層、輸出層，和若干個中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。蘭蘭規(guī)定，Ci服從公式(1)（其中n是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目）公式中的Wji（可能為負值）表示連接j號神經(jīng)元和i號神經(jīng)元的邊的權(quán)值。當(dāng)Ci大于0時，該神經(jīng)元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時，下一秒它會向其他神經(jīng)元傳送信號，信號的強度為Ci。如此．在輸入層神經(jīng)元被激發(fā)之后，整個網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿酉逻M行運作。現(xiàn)在，給定一個神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)Ci，要求你的程序運算出最后網(wǎng)絡(luò)輸出層的狀態(tài)。

【輸入格式】第一行是兩個整數(shù)n（1≤n≤20）和p。接下來n行，每行兩個整數(shù)，第i＋1行是神經(jīng)元i最初狀態(tài)和其閾值（Ui），非輸入層的神經(jīng)元開始時狀態(tài)必然為0。再下面P行，每行由兩個整數(shù)i，j及一個整數(shù)Wij，表示連接神經(jīng)元i、j的邊權(quán)值為Wij【輸出格式】輸出包含若干行，每行有兩個整數(shù)，分別對應(yīng)一個神經(jīng)元的編號，及其最后的狀態(tài)，兩個整數(shù)間以空格分隔。僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號由小到大順序輸出！若輸出層的神經(jīng)元最后狀態(tài)均為0，則輸出NULL。分析

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

由于階段圖的性質(zhì)使得該圖的所有邊所連接節(jié)點的等級都是相鄰的，因此就可以設(shè)計出一個基于寬度優(yōu)先搜索（即BFS）的算法：1．初始時將所有輸入層的節(jié)點放入隊列；2．取出隊列中的一個元素，不重復(fù)地擴展并處理該節(jié)點所發(fā)出的邊的目標(biāo)節(jié)點；3．如果隊列非空，則轉(zhuǎn)向2；4．輸出輸出層中所有滿足條件的節(jié)點。但是由于本題在問題描述中并沒有明確的給出判斷一個節(jié)點是否是輸入節(jié)點，因此需要在算法進行的過程當(dāng)中額外地考慮一些邊界情況的數(shù)據(jù)（這個過程即便是真實數(shù)據(jù)沒有這樣出也是要有的），下面給出的更一般的算法可能會更好的跳過這些邊界情況。1．對原圖中所有的節(jié)點進行一次拓撲排序；2．按照拓撲順序處理每一個節(jié)點；3．輸出輸出層中所有滿足條件的節(jié)點。思考題2:聰明的打字員阿蘭是某機密部門的打字員，她現(xiàn)在接到一個任務(wù)：需要在一天之內(nèi)輸入幾百個長度固定為6的密碼。當(dāng)然，她希望輸入的過程中敲擊鍵盤的總次數(shù)越少越好。不幸的是，出于保密的需要，該部門用于輸入密碼的鍵盤是特殊設(shè)計的，鍵盤上沒有數(shù)字鍵，而只有以下六個鍵：Swap0,Swap1,Up,Down,Left,Right，為了說明這6個鍵的作用，我們先定義錄入?yún)^(qū)的6個位置的編號，從左至右依次為1，2，3，4，5，6。下面列出每個鍵的作用：Swap0：按Swap0，光標(biāo)位置不變，將光標(biāo)所在位置的數(shù)字與錄入?yún)^(qū)的1號位置的數(shù)字（左起第一個數(shù)字）交換。如果光標(biāo)已經(jīng)處在錄入?yún)^(qū)的1號位置，則按Swap0鍵之后，錄入?yún)^(qū)的數(shù)字不變；Swap1：按Swap1，光標(biāo)位置不變，將光標(biāo)所在位置的數(shù)字與錄入?yún)^(qū)的6號位置的數(shù)字（左起第六個數(shù)字）交換。如果光標(biāo)已經(jīng)處在錄入?yún)^(qū)的6號位置，則按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)左移一個位置，如果光標(biāo)已經(jīng)在錄入?yún)^(qū)的1號位置（左起第一個位置）上，則光標(biāo)不動；Right：按Right，光標(biāo)右移一個位置，如果光標(biāo)已經(jīng)在錄入?yún)^(qū)的6號位置（左起第六個位置）上，則光標(biāo)不動。當(dāng)然，為了使這樣的鍵盤發(fā)揮作用，每次錄入密碼之前，錄入?yún)^(qū)總會隨機出現(xiàn)一個長度為6的初始密碼，而且光標(biāo)固定出現(xiàn)在1號位置上。當(dāng)巧妙地使用上述六個特殊鍵之后，可以得到目標(biāo)密碼，這時光標(biāo)允許停在任何一個位置?，F(xiàn)在，阿蘭需要你的幫助，編寫一個程序，求出錄入一個密碼需要的最少的擊鍵次數(shù)。擴展規(guī)則設(shè)當(dāng)前狀態(tài)為(S,index)，下一個狀態(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）表示問題中的一個狀態(tài)，S為密碼，index表示光標(biāo)位置。那么，（Source，1）為問題的初始狀態(tài)，（Target，pos）為問題的目標(biāo)狀態(tài)。其中pos任意。那么綜合數(shù)據(jù)庫中可能存在的節(jié)點數(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;{隊列}app:array[1..6,0..9,0..9,0..9,0..9,0..9,0..9]ofboolean;{判重數(shù)組}final:statetype;{目標(biāo)狀態(tài)}算法選擇closed:=0;ope