宽度优先搜索课件

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

八数码问题宽度优先算法框架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;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;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.兰兰规定，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之后，数字不变，光标位置也不变；扩展规则设当前状态为(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;{目标状态}思考题3:AmazingRobots已知条件：

迷宫i（i=1,2）（每个不会大于20*20）守卫Gi（0<=Gi<=10）（守卫循环移动进行执勤）（守卫巡逻的方格数（2..4））求：

两个机器人都离开迷宫所用的最少指令数目和离开制指令序列（10000步以内）。方法1每一步可以发出的命令可以是N,E,S,W中的一种，有4种选择。对每一步具体发出哪个命令，直接搜索。假设最后结果是T。（也就是最少出宫时间）时间复杂度是O(4T)这种方法时间复杂度太高，绝对不可行!!思考?5*4和4*4的迷宫第一个机器人的位置是(2,2)第二个机器人的位置是(3,2)当前时间是0。状态((2,2),(3,2),0)状态表示：（第一个机器人位置，第二个机器认位置，时间）E((2,2),(3,2),0)((2,3),(3,3),1)时间已知，则所有Guard的位置可知。Guard、Robot的位置均已知，所以状态可以转移0时刻1时刻2时刻3时刻0时刻和2时刻是一样的1时刻和3时刻是一样的。稍加分析：此Guard循环以2为周期循环。状态转移，需要的信息是：Robot位置，Guard位置。PositionofRobot1,2是的作用就是记录Robot位置。Time的作用就是为了计算Guard的位置状态：(positionofRobot1,positionofRobot2,Time)Time<=10000，这是状态数过多的罪魁祸首！题目说：Guard巡逻经过的格子数只可能是2,3,4。也就是说机器人巡逻周期只能是2,4,6。[2,4,6]=12，所以第0时刻、12时刻、24时刻，Guard的状态完全相同。12可以看作Guard的周期。Time只要记录当前是第几个周期。因为周期确定了，Guard的位置也完全确定了！0<=Time<=11状态数(n*n)*(n*n)*12=12n4。用BFS算法，标志数组判重。时间复杂度O(12n4)。n<=20完全可以承受^-^思考题4：街道赛跑下图给出了一个沿街道赛跑的路线。图中有许多点，给以标号0，1，．．．N(此图中N=9)，点之间可以用含箭头的线相连。标号为0的点是起点；标号为N的点为终点。含箭头的线表示单向通行的街道。运动员沿箭头所指方向从一个点跑向另一个点；在每一个点上，运动员可以选择任何一个箭头(向外的)继续向前跑。一个完整路线具有如下特点：1．路线中每一点都可从出发点到达；2．路线中每一点都可到达终点；3．终点处没有向外的箭头。运动员要到达终点，但不要求路线（图）中的每一点都经过。但是路线(图)中的某些点是必经之点。上图的例子中，必经之点是：0，3，6，9。任务A:题目给出一个完整路线（图），请编程找出所有必经之点。请注意，输出必经之点时，应不包括起点和终点。任务B:假定赛跑必须在相邻的2天来举行。因此，要把原来给定的完整路线（图）分成两个子路线（图）。第1天从点0出发，结束于“分裂点”。第2天从“分裂点”出发，结束于点N。题目给出一个完整路线（图）C，请编程输出所有可能的“分裂点”（任务B）。“分裂点”S一定不是起点或终点。C可被S分成两个完整的子路线：这两个子路线没有公共的箭头线，并且S是这两个子路线的唯一公共点。在上的例子中，仅点3是“分裂点”。输入数据： 输入数据描述一个完整路线（最多50个点，最多100个箭头），共n＋1行。前面n行描述箭头的终点，其中第i行中的每一个数字表示从点i（1≤i≤n）出发的每一个箭头的终点，以－2作为该行的结束。最后一行（第n+1行）中有一个数字－1，表示输入结束。输出数据： 输出两行数据，第1行表示必经点（子任务A）──首先是必经点的总数，其后是必经点的标号，标号的顺序无关紧要。第2行表示“分裂点”：首先是分裂点的总数，其后是分裂点的标号，标号出现的先后顺序无关紧要（子任务B）。分析必经点: 是指运动员从起点0出发，沿箭头方向跑，无论走哪条路线，都经由该点到达终点N。所有这些点组成必经点的集合。反之，在完整路线中去除必经点集合中的任一个点，无论运动员选择哪条路线跑，都不可能从起点0跑至终点N。分裂点:①某点是必经点；②在完整路线中去除这个必经点后，由起点出发的运动员无论如何也不会跑到由这个必经点出发的任一箭头的终点；③完整路线中去除这个必经点后的所有点，分成两个互为独立的集合: