宽度优先搜索

宽度优先搜索应用实例长沙市雅礼中学朱全民知识重点宽度优先算法的基本原理与构造方法宽度优先算法的实现状态空间的描述宽度优先算法的应用宽度有先算法的优化方法宽度优先搜索框架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);八数码问题

在3*3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1—8中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格中移动，如右图所示。这样通过移动将牌就可以不断改变的布局结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状态），问如何移动将牌，才能实现从初始状态到目标状态的转换。状态空间描述{Pxy}，其中1<=x,y<=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等

用Pascal语言描述如下：typeT8no=array[1..3,1..3]ofinteger;{棋盘状态}TList=record{描述一个节点}Father:integer;{父指针}dep:byte;{深度}x,y:byte; {空格的位置}state:T8no; end;constMax=10000;vars,t:T8no;{s为初始状态，t为目标状态}List:array[0..max]ofTList;{所有结点}扩展规则if条件then规则；设Pxy表示将牌第x行第y列的数码，m,n表示数码空格所在的行列值，记Pm,n=0,则可以得到如下四条规则：

①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{对应四种产生式规则}=((1,0),(-1,0),(0,1),(0,-1));八数码问题宽度优先扩展过程

八数码问题宽度优先算法框架List[1]=source;closed:=0;open:=1;{加入初始节点,List为扩展节点的表}Repeatclosed:=closed+1;n:=List[closed];{取出closed对应的节点}Forx:=1to4do[new:=Move(n,x);{对n节点使用第x条规则，得到new}ifnot_Appear(new,List)then[{如果new没有在List中出现}open:=open+1;List[open]:=new;{加入新节点到open}List[open].Father:=closed;{修改指针}ifList[open]=GoalthenGetOut;];]Untilclosed=open;program8no_bfs;{八数码的宽度优先搜索算法}ConstDir:array[1..4,1..2]ofinteger{四种移动方向，对应产生式规则}=((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; {棋盘状态}end;VarSource,Target:T8no;List:array[0..10000]ofTList;{综合数据库}Closed,open,Best:integer{Best表示最优移动次数}Answer:integer;{记录解}Found:Boolean;{解标志}procedureGetInfo;{读入初始和目标节点}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状态是否相等}Vari,j:integer;BeginSame:=false;Fori:=1to3doforj:=1to3doifA[i,j]<>B[i,j]thenexit;Same:=true;End;functionnot_Appear(new:tList):boolean;{判断new是否在List中出现}vari:integer;beginnot_Appear:=false;fori:=1toopendoifSame(new.State,List[i].State)thenexit;not_Appear:=true;end;procedureAdd(new:tList);{插入节点new}beginifnot_Appear(new)thenBegin{如果new没有在List出现}Inc(open);{new加入open表}List[open]:=new;end;end;procedureMove(n:tList;d:integer;varok:boolean;varnew:tList);{将第d条规则作用于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的子节点}vari:integer;new:tList;OK:boolean;BeginifSame(n.State,Target)thenbegin{如果找到解}Found:=true;Best:=n.Dep;Answer:=Index;Exit;end;Fori:=1to4dobegin{依次使用４条规则}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:神经网络在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：图中，X1—X3是信息输入渠道，Y1－Y2是信息输出渠道，C1表示神经元目前的状态，Ui是阈值，可视为神经元的一个内在参数。神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。兰兰规定，Ci服从公式(1)（其中n是网络中所有神经元的数目）公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态Ci，要求你的程序运算出最后网络输出层的状态。

【输入格式】第一行是两个整数n（1≤n≤20）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij【输出格式】输出包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！若输出层的神经元最后状态均为0，则输出NULL。分析

理解问题的第一步就是认真“读题”。那么我们先来看一看这个题目涉及的问题。研究一下题目中所给的图的一些性质，可以发现如下特点：1．图中所有的节点都有一个确定的等级，我们记作Level(i)2．图中所有的边都是有向的，并且从Level值为i-1的节点指向Level值为i的节点我们不妨将其抽象为“阶段图”。更一般地，我们可以发现所有的阶段图都是有向无环的，这样我们可以通过拓扑排序来得到期望的处理节点的顺序。可行算法

由于阶段图的性质使得该图的所有边所连接节点的等级都是相邻的，因此就可以设计出一个基于宽度优先搜索（即BFS）的算法：1．初始时将所有输入层的节点放入队列；2．取出队列中的一个元素，不重复地扩展并处理该节点所发出的边的目标节点；3．如果队列非空，则转向2；4．输出输出层中所有满足条件的节点。但是由于本题在问题描述中并没有明确的给出判断一个节点是否是输入节点，因此需要在算法进行的过程当中额外地考虑一些边界情况的数据（这个过程即便是真实数据没有这样出也是要有的），下面给出的更一般的算法可能会更好的跳过这些边界情况。1．对原图中所有的节点进行一次拓扑排序；2．按照拓扑顺序处理每一个节点；3．输出输出层中所有满足条件的节点。思考题2:聪明的打字员阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0,Swap1,Up,Down,Left,Right，为了说明这6个键的作用，我们先定义录入区的6个位置的编号，从左至右依次为1，2，3，4，5，6。下面列出每个键的作用：Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的1号位置，则按Swap0键之后，录入区的数字不变；Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的6号位置，则按Swap1键之后，录入区的数字不变；Up：按Up，光标位置不变，将光标所在位置的数字加1（除非该数字是9）。例如，如果光标所在位置的数字为2，按Up之后，该处的数字变为3；如果该处数字为9，则按Up之后，数字不变，光标位置也不变；Down：按Down，光标位置不变，将光标所在位置的数字减1（除非该数字是0），如果该处数字为0，则按Down之后，数字不变，光标位置也不变；Left：按Left，光标左移一个位置，如果光标已经在录入区的1号位置（左起第一个位置）上，则光标不动；Right：按Right，光标右移一个位置，如果光标已经在录入区的6号位置（左起第六个位置）上，则光标不动。当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为6的初始密码，而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。扩展规则设当前状态为(S,index)，下一个状态为(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;]数据结构的处理 如果我们用（S,index）表示问题中的一个状态，S为密码，index表示光标位置。那么，（Source，1）为问题的初始状态，（Target，pos）为问题的目标状态。其中pos任意。那么综合数据库中可能存在的节点数为：6*106。constmaxl=6000000;typestatetype=array[1..6]ofshortint;Nodetype=recordstate:statetype;{密码}point,step:shortint;{光标位置，按键次数}end;varq:array[0..maxl]ofNodetype;{队列}app:array[1..6,0..9,0..9,0..9,0..9,0..9,0..9]ofboolean;{判重数组}final:statetype;{目标状态}算法选择closed:=0;ope