寬度優(yōu)先搜索-PPT幻燈片

知識重點寬度優(yōu)先算法的基本原理與構造方法寬度優(yōu)先算法的實現(xiàn)狀態(tài)空間的描述寬度優(yōu)先算法的應用寬度有先算法的優(yōu)化方法寬度優(yōu)先搜索框架PROCEDUREBFS-SEARCH;1.

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

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

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

Repeat5.

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

ifn=GoalthenExit(Success);

7.

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

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

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

Untilclosed=open;

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

在3*3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有1—8中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格中移動，如右圖所示。這樣通過移動將牌就可以不斷改變的布局結構，給出一個初始布局（稱初始狀態(tài)）和一個目標布局（稱目標狀態(tài)），問如何移動將牌，才能實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉換。八數(shù)碼問題寬度優(yōu)先擴展過程

八數(shù)碼問題寬度優(yōu)先算法框架List[1]=source;closed:=0;open:=1;{加入初始節(jié)點,List為擴展節(jié)點的表}Repeatclosed:=closed+1;n:=List[closed];{取出closed對應的節(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{四種移動方向，對應產(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;{解標志}procedureGetInfo;{讀入初始和目標節(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是否可行的標志}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)絡在蘭蘭的模型中，神經(jīng)網(wǎng)絡就是一張有向圖，圖中的節(jié)點稱為神經(jīng)元，而且兩個神經(jīng)元之間至多有一條邊相連，下圖是一個神經(jīng)元的例子：圖中，X1—X3是信息輸入渠道，Y1－Y2是信息輸出渠道，C1表示神經(jīng)元目前的狀態(tài)，Ui是閾值，可視為神經(jīng)元的一個內(nèi)在參數(shù)。神經(jīng)元按一定的順序排列，構成整個神經(jīng)網(wǎng)絡。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡中的神經(jīng)無分為幾層；稱為輸入層、輸出層，和若干個中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。蘭蘭規(guī)定，Ci服從公式(1)（其中n是網(wǎng)絡中所有神經(jīng)元的數(shù)目）公式中的Wji（可能為負值）表示連接j號神經(jīng)元和i號神經(jīng)元的邊的權值。當Ci大于0時，該神經(jīng)元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當神經(jīng)元處于興奮狀態(tài)時，下一秒它會向其他神經(jīng)元傳送信號，信號的強度為Ci。如此．在輸入層神經(jīng)元被激發(fā)之后，整個網(wǎng)絡系統(tǒng)就在信息傳輸?shù)耐苿酉逻M行運作?，F(xiàn)在，給定一個神經(jīng)網(wǎng)絡，及當前輸入層神經(jīng)元的狀態(tài)Ci，要求你的程序運算出最后網(wǎng)絡輸出層的狀態(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的邊權值為Wij【輸出格式】輸出包含若干行，每行有兩個整數(shù)，分別對應一個神經(jīng)元的編號，及其最后的狀態(tài)，兩個整數(shù)間以空格分隔。僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號由小到大順序輸出！若輸出層的神經(jīng)元最后狀態(tài)均為0，則輸出NULL。分析

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

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

迷宮i（i=1,2）（每個不會大于20*20）守衛(wèi)Gi（0<=Gi<=10）（守衛(wèi)循環(huán)移動進行執(zhí)勤）（守衛(wèi)巡邏的方格數(shù)（2..4））求：

兩個機器人都離開迷宮所用的最少指令數(shù)目和離開制指令序列（10000步以內(nèi)）。方法1每一步可以發(fā)出的命令可以是N,E,S,W中的一種，有4種選擇。對每一步具體發(fā)出哪個命令，直接搜索。假設最后結果是T。（也就是最少出宮時間）時間復雜度是O(4T)這種方法時間復雜度太高，絕對不可行!!思考?5*4和4*4的迷宮第一個機器人的位置是(2,2)第二個機器人的位置是(3,2)當前時間是0。狀態(tài)((2,2),(3,2),0)狀態(tài)表示：（第一個機器人位置，第二個機器認位置，時間）E((2,2),(3,2),0)((2,3),(3,3),1)時間已知，則所有Guard的位置可知。Guard、Robot的位置均已知，所以狀態(tài)可以轉移0時刻1時刻2時刻3時刻0時刻和2時刻是一樣的1時刻和3時刻是一樣的。稍加分析：此Guard循環(huán)以2為周期循環(huán)。狀態(tài)轉移，需要的信息是：Robot位置，Guard位置。PositionofRobot1,2是的作用就是記錄Robot位置。Time的作用就是為了計算Guard的位置狀態(tài)：(positionofRobot1,positionofRobot2,Time)Time<=10000，這是狀態(tài)數(shù)過多的罪魁禍首！題目說：Guard巡邏經(jīng)過的格子數(shù)只可能是2,3,4。也就是說機器人巡邏周期只能是2,4,6。[2,4,6]=12，所以第0時刻、12時刻、24時刻，Guard的狀態(tài)完全相同。12可以看作Guard的周期。Time只要記錄當前是第幾個周期。因為周期確定了，Guard的位置也完全確定了！0<=Time<=11狀態(tài)數(shù)(n*n)*(n*n)*12=12n4。用BFS算法，標志數(shù)組判重。時間復雜度O(12n4)。n<=20完全可以承受^-^思考題4：街道賽跑下圖給出了一個沿街道賽跑的路線。圖中有許多點，給以標號0，1，．．．N(此圖中N=9)，點之間可以用含箭頭的線相連。標號為0的點是起點；標號為N的點為終點。含箭頭的線表示單向通行的街道。運動員沿箭頭所指方向從一個點跑向另一個點；在每一個點上，運動員可以選擇任何一個箭頭(向外的)繼續(xù)向前跑。一個完整路線具有如下特點：1．路線中每一點都可從出發(fā)點到達；2．路線中每一點都可到達終點；3．終點處沒有向外的箭頭。運動員要到達終點，但不要求路線（圖）中的每一點都經(jīng)過。但是路線(圖)中的某些點是必經(jīng)之點。上圖的例子中，必經(jīng)之點是：0，3，6，9。任務A:題目給出一個完整路線（圖），請編程找出所有必經(jīng)之點。請注意，輸出必經(jīng)之點時，應不包括起點和終點。任務B:假定賽跑必須在相鄰的2天來舉行。因此，要把原來給定的完整路線（圖）分成兩個子路線（圖）。第1天從點0出發(fā)，結束于“分裂點”。第2天從“分裂點”出發(fā)，結束于點N。題目給出一個完整路線（圖）C，請編程輸出所有可能的“分裂點”（任務B）。“分裂點”S一定不是起點或終點。C可被S分成兩個完整的子路線：這兩個子路線沒有公共的箭頭線，并且S是這兩個子路線的唯一公共點。在上的例子中，僅點3是“分裂點”。輸入數(shù)據(jù)： 輸入數(shù)據(jù)描述一個完整路線（最多50個點，最多100個箭頭），共n＋1行。前面n行描述箭頭的終點，其中第i行中的每一個數(shù)字表示從點i（1≤i≤n）出發(fā)的每一個箭頭的終點，以－2作為該行的結束。最后一行（第n+1行）中有一個數(shù)字－1，表示輸入結束。輸出數(shù)據(jù)： 輸出兩行數(shù)據(jù)，第1行表示必經(jīng)點（子任務A）──首先是必經(jīng)點的總數(shù)，其后是必經(jīng)點的標號，標號的順序無關緊要。第2行表示“分裂點”：首先是分裂點的總數(shù)，其后是分裂點的標號，標號出現(xiàn)的先后順序無關緊要（子任務B）。分析必經(jīng)點: 是指運動員從起點0出發(fā)，沿箭頭方向跑，無論走哪條路線，都經(jīng)由該點到達終點N。所