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

知識(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ù)碼問題

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

八數(shù)碼問題寬度優(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,x);{對(duì)n節(jié)點(diǎn)使用第x條規(guī)則，得到new}ifnot_Appear(new,List)then[{如果new沒有在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; {棋盤狀態(tài)}end;VarSource,Target:T8no;List:array[0..10000]ofTList;{綜合數(shù)據(jù)庫}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沒有在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;{搜索主過程}beginRepeatInc(Closed);Expand(Closed,List[Closed]);{擴(kuò)展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é)點(diǎn)稱為神經(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)無分為幾層；稱為輸入層、輸出層，和若干個(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。接下來n行，每行兩個(gè)整數(shù)，第i＋1行是神經(jīng)元i最初狀態(tài)和其閾值（Ui），非輸入層的神經(jīng)元開始時(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。分析

理解問題的第一步就是認(rèn)真“讀題”。那么我們先來看一看這個(gè)題目涉及的問題。研究一下題目中所給的圖的一些性質(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)所有的階段圖都是有向無環(huán)的，這樣我們可以通過拓?fù)渑判騺淼玫狡谕奶幚砉?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．輸出輸出層中所有滿足條件的節(jié)點(diǎn)。但是由于本題在問題描述中并沒有明確的給出判斷一個(gè)節(jié)點(diǎn)是否是輸入節(jié)點(diǎn)，因此需要在算法進(jìn)行的過程當(dāng)中額外地考慮一些邊界情況的數(shù)據(jù)（這個(gè)過程即便是真實(shí)數(shù)據(jù)沒有這樣出也是要有的），下面給出的更一般的算法可能會(huì)更好的跳過這些邊界情況。1．對(duì)原圖中所有的節(jié)點(diǎn)進(jìn)行一次拓?fù)渑判颍?．按照拓?fù)漤樞蛱幚砻恳粋€(gè)節(jié)點(diǎn)；3．輸出輸出層中所有滿足條件的節(jié)點(diǎn)。思考題2:聰明的打字員阿蘭是某機(jī)密部門的打字員，她現(xiàn)在接到一個(gè)任務(wù)：需要在一天之內(nèi)輸入幾百個(gè)長度固定為6的密碼。當(dāng)然，她希望輸入的過程中敲擊鍵盤的總次數(shù)越少越好。不幸的是，出于保密的需要，該部門用于輸入密碼的鍵盤是特殊設(shè)計(jì)的，鍵盤上沒有數(shù)字鍵，而只有以下六個(gè)鍵：Swap0,Swap1,Up,Down,Left,Right，為了說明這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)然，為了使這樣的鍵盤發(fā)揮作用，每次錄入密碼之前，錄入?yún)^(qū)總會(huì)隨機(jī)出現(xiàn)一個(gè)長度為6的初始密碼，而且光標(biāo)固定出現(xiàn)在1號(hào)位置上。當(dāng)巧妙地使用上述六個(gè)特殊鍵之后，可以得到目標(biāo)密碼，這時(shí)光標(biāo)允許停在任何一個(gè)位置。現(xiàn)在，阿蘭需要你的幫助，編寫一個(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）表示問題中的一個(gè)狀態(tài)，S為密碼，index表示光標(biāo)位置。那么，（Source，1）為問題的初始狀態(tài)，（Target，pos）為問題的目標(biāo)狀態(tài)。其中pos任意。那么綜合數(shù)據(jù)庫中可能存在的節(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)的話}調(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:AmazingRobots已知條件：

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

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