宽度优先搜索.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,知识重点,宽度优先算法的基本原理与构造方法,宽度优先算法的实现,状态空间的描述,宽度优先算法的应用,宽度有先算法的优化方法,宽度优先搜索框架,PROCEDURE BFS-SEARCH;,1.,G:=G,0,;初始化图,2.,closed:=(Source);队首指针指向初始结点,3.,open,:=(Source);队尾指针指向空,4.,Repeat,5.,n:=GET(closed)取出closed指向的结点,记为n,6.,if n=Goal then Exit(Success);,7.,while n能扩展 do ,8,m:=Expand(n);扩展取出的结点,9.,inc(open);Add(m,open);队尾指针后移,并插入队列,10.,Add(m,G);构图,11.,inc(closed);队首指针后移,12.,Until closed=open;,13.,Exit(Fail);,八数码问题,在,3*3,组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有,18,中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格中移动，如右图所示。这样通过移动将牌就可以不断改变的布局结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状态），问如何移动将牌，才能实现从初始状态到目标状态的转换。,八数码问题宽度优先扩展过程,八数码问题宽度优先算法框架,List1=source;closed:=0;open:=1;,加入初始节点,List为扩展节点的表,Repeat,closed:=closed+1;n:=Listclosed;取出closed对应的节点,For x:=1 to 4 do,new:=Move(n,x);对n节点使用第x条规则，得到new,if not_Appear(new,List)then 如果new没有在List中出现,open:=open+1;Listopen:=new;加入新节点到open,Listopen.Father:=closed;修改指针,if Listopen=Goal then GetOut;,;,Until closed=open;,program 8no_bfs;八数码的宽度优先搜索算法,Const,Dir:array1.4,1.2of integer 四种移动方向，对应产生式规则,=(1,0),(-1,0),(0,1),(0,-1);,n=10000;,Type,T8no=array1.3,1.3of integer;,TList=record,Father:integer;父指针,dep:byte;深度,X0,Y0:byte;0的位置,State:T8no;棋盘状态,end;,Var,Source,Target:T8no;,List:array0.10000 of TList;综合数据库,Closed,open,Best:integer Best表示最优移动次数,Answer:integer;记录解,Found:Boolean;解标志,procedure GetInfo;读入初始和目标节点,var i,j:integer;,procedure Initialize;初始化,var x,y:integer;,begin,for i:=1 to 3 do,for j:=1 to 3 do read(Sourcei,j);,for i:=1 to 3 do,for j:=1 to 3 do read(Targeti,j);,Found:=false;,Closed:=0;open:=1;,with List1 do begin,State:=Source;dep:=0;Father:=0;,For x:=1 to 3 do,For y:=1 to 3 do,if Statex,y=0 then Begin x0:=x;y0:=y;End;,end;,end;,Function Same(A,B:T8no):Boolean;判断A,B状态是否相等,Var i,j:integer;,Begin,Same:=false;,For i:=1 to 3 do for j:=1 to 3 do if Ai,jBi,j then exit;,Same:=true;,End;,function not_Appear(new:tList):boolean;判断new是否在List中出现,var i:integer;,begin,not_Appear:=false;,for i:=1 to open do if Same(new.State,Listi.State)then exit;,not_Appear:=true;,end;,procedure Add(new:tList);插入节点new,begin,if not_Appear(new)then Begin 如果new没有在List出现,Inc(open);new加入open表,Listopen:=new;,end;,end;,procedure Move(n:tList;d:integer;var ok:boolean;var new:tList);,将第d条规则作用于n得到new,OK是new是否可行的标志,var x,y:integer;,begin,X:=n.x0+Dird,1;Y:=n.y0+Dird,2;,if not(X 0)and(X 0)and(Y=open)or Found;,if Found then GetOutInfo 存在解,else Writeln(no answer);无解,end;,Begin,Assign(Input,input.txt);ReSet(Input);,Assign(Output,Output.txt);ReWrite(Output);,GetInfo;,Initialize;,Main;,Close(Input);Close(Output);,End.,思考题1:神经网络,在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：,图中，X1X3是信息输入渠道，Y1Y2是信息输出渠道，C1表示神经元目前的状态，Ui是阈值，可视为神经元的一个内在参数。,神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。,兰兰规定，C,i,服从公式(1)（其中n是网络中所有神经元的数目）,公式中的W,ji,（可能为负值）表示连接j号神经元和 i号神经元的边的权值。当 Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。如此在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态Ci，要求你的程序运算出最后网络输出层的状态。,【输入格式】,第一行是两个整数n（1n20）和p。接下来n行，每行两个整数，第i1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为W,ij,【输出格式】,输出包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。,仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！,若输出层的神经元最后状态均为 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：,if index1 then,S,:=S;S,1:=Sindex;S,index:=S1;Index,:=index;,Swap1：,if index6 then,S,:=S;S,6:=Sindex;S,index:=S6;Index,:=index;,Up：,if Sindex9 then S,:=S;S,index:=S,index+1;Index,:=index;,Down：,if Sindex0 then S,:=S;S,index:=S,index-1;Index,:=index;,Left：,if index0 then S,:=S;Index,:=index-1;,Right：,if index6 then S,:=S;Index,:=index+1;,数据结构的处理,如果我们用（S,index）表示问题中的一个状态，S为密码，index表示光标位置。那么，（Source，1）为问题的初始状态，（Target，pos）为问题的目标状态。其中pos任意。那么综合数据库中可能存在的节点数为：6*10,6,。,const maxl =6000000;,type,statetype =array1.6 of shortint;,Nodetype =record,state:statetype;密码,point,step:shortint;光标位置，按键次数,end;,var,q :array0.maxl of Nodetype;队列,app:array1.6,0.9,0.9,0.9,0.9,0.9,0.9 of boolean;判重数组,final :statetype;目标状态,算法选择,closed:=0;open:=1;,q1.point:=1;,fillchar(app,sizeof(app),false);,while true do begin,closed:=closed mod maxl+1;,with qclosed do begin,if comparebyte(state,final,6)=0 then 打印输出；如果是目标的话,调用6条规则扩展出state新节点；,if not apppoint,state1,state2,state3,state4,state5,state6 判重,then begin,open:=open mod maxl+1;,qopen.state:=state;,qopen.step:=step+1;,qopen.point:=point;,apppoint,state1,state2,state3,state4,state5,state6:=true;,end;,思考题3:Amazing Robots,已知条件：,迷宫,i（i=1,2）,（每个不会大于20*20）,守卫,Gi（0=Gi=10）,（守卫循环移动进行执勤）,（守卫巡逻的方格数（2.4）,求：,两个机器人都离开迷宫所用的最少指令数目,和离开制指令序列（10000 步以内）。,方法1,每一步可以发出的命令可以是N,E,S,W中的一种，有4种选择。,对每一步具体发出哪个命令，直接搜索。,假设最后结果是T。（也就是最少出宫时间）,时间复杂度是O(4,T,),这种方法时间复杂度太高，绝对不可行!,思考?,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,位置。,Position of Robot1,2,是的作用就是记录,Robot,位置。,Time,的作用就是为了计算,Guard,的位置,状态：,(position of Robot1,position of Robot2,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=12n,4,。,用,BFS,算法，标志数组判重。,时间复杂度,O(12n,4,),。,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个箭头），共n1行。前面n行描述箭头的终点，其中第i行中的每一个数字表示从点i（1in）出发的每一个箭头的终点，以2作为该行的结束。最后一行（第n+1行）中有一个数字1，表示输入结束。,输出数据：,输出两行数据，第1行表示必经点（子任务A）首先是必经点的总数，其后是必经点的标号，标号的顺序无关紧要。第2行表示“分裂点”：首先是分裂点的总数，其后是分裂点的标号，标号出现的先后顺序无关紧要（子任务B）。,分析,必经点:,是指运动员从起点0出发，沿箭头方向跑，无论走哪条路线，都经由该点到达终点N。所有这些点组成必经点的集合。反之，在完整路线中去除必经点集合中的任一个点，无论运动员选择哪条路线跑，都不可能从起点0跑至终点N。,分裂点:,某点是必经点；,在完整路线中去除这个必经点后，由起点出发的运动员无论如何也不会跑到由这个必经点出发的任一箭头的终点；,完整路线中去除这个必经点后的所有点，分成两个互为独立的集合:,可从出发点0到达。这些点组成子路径1；,无法从出发点0到达。这些点组成子路径2；,两个集合中的点之间，无任何箭头相连；,思路,从点0开始，按逐层搜索的方法对删除当前判别点后的路线重复进行访问，直至找不到可访问的点为止。广度搜索的结果，将路线上的所有点(除当前判别点外)分为两个集合：,宽度优先搜索中访问到的点，即从出发点0可达的点集合，设这些点到达标志；,宽度优先搜索中未访问过的点，即不可从出发点0到达的点集合。这些点设未到达标志；,若终点N在第二个集合中，则当前判别点是必经点，然后再判别两个集合是否互为独立。若与必经点相连的所有点都在第二个集合中，且两个集合中的点之间无任何箭头相连，则这个必经点亦是分裂点。,算法描述,输入完整路线的相邻矩阵data1;,For i1 to n-1 do /顺序设点1、点2，点N1为当前判别点,begin,datadata1;/删除顶点i，构建新图的相邻矩阵data；,for j1 to n do begin datai,j0;dataj,i0 end;,BFS(0)；/宽度优先搜索出发点0可达的点集,if visitedn=-1 /若出发点0不可达终点n，则顶点i为必经点,then begin,输出顶点i为必经点；,foundtrue；/初始时假设顶点i为分裂点,For k0 to n-1 do /搜索出发点0可达的点集合,For p0 to n do /搜索出发点0不可达的点集合,if (visitedk-1)&(visitedp=-1)&(datak,p0)|(datap,k0),then begin /若两个点集间有边相连，则退出for循环,foundfalse;break;,end;,if found then 输出顶点i为分裂点；,end；then,end；for,