广度优先搜索算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,广度优先搜索算法,1,例 八数码难题。,在33的棋盘上，摆 有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始布局初始状态和目标布局目标状态，找到一种移动的方法，实现从初始布局到目标布局的转变。,2 8 3,1 6 4,7 5,1 2 3,8 4,7 6 5,2,283,164,705,283,164,075,283,164,750,283,104,765,283,064,175,283,014,765,203,184,765,283,140,765,283,164,750,083,264,175,283,604,175,083,214,765,283,714,065,280,143,765,283,145,760,283,106,754,283,163,754, ,3,综合数据库,type,node=record,ch:array1.3,1.3 of byte;,si,sj:byte;空格的坐标,pnt,dep:word;父节点和深度,end;,Var,data:array1.2600 of node;,temp:node;,4,产生式规则:,4条，空格向上，下，左，右四个方向移动,生成结点的条件：,（1）新状态不出界,（2）和已生成结点不重复,ni:=temp.si+dik;nj:=temp.sj+djk;,with temp do,begin,chsi,sj:=chni,nj;,chni,nj:=0;si:=ni;sj:=nj;,pnt:=head;dep:=dep+1;,end;,r,1,2,3,4,方向,左,上,右,下,di,0,-1,0,1,dj,-1,0,1,0,5,搜索策略,（BFS）,框图：,初始,head=0,Tail=0,初始化INIT;初始结点入队,结点出队out(temp1),temp temp1 change(temp),For r:=1 to 4 do,Check(temp) and not(dupe(temp),y,n,In(temp),Temp=goal,y,n,Print 打印,Exit 退出,Until head=tail,6,练习：,有两个无刻度标志的水壶，分别可装5升水和2升水，设另有一水缸，可用来向水壶灌水或倒出水，两水壶间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶。问如何通过倒水或灌水操作，用最少步数能在2升壶中量出1升水来。编一程序解决问题。,7,如图是六个城市之间道路联系的示意图，连线表示两城市间有道路相通，连线旁的数字表示路程。请编程序，由计算机找到从C1到C6的一条路径及路程总长度，要求求出经过城市最少的解和路程总长度最少的解。,C6,3,4,4,8,4,9,2,2,6,4,C1,C2,C5,C4,C3,8,综合数据库,type,node=record,city:integer;城市编号,flag:set of 1.6;到根结点的路径,pnt:integer;父节点,end;,Var,data:array1.1000 of node;,temp:node;,9,产生式规则:,5条，向R（R=2-6）城市移动,生成结点的条件：,（1）城市R不在已走路径中（not(R in datahead.flag)）,（2）当前城市到R有路（linkx,r0）,Datatemp.city:=R;,Datatemp.flag:= Datatemp.flag+R;,Datatemp.pnt:=head;,10,搜索策略,（BFS）,框图：,初始,head=0,Tail=0,初始化INIT;初始结点入队,结点出队out(temp),temp1 temp change(temp),For r:=2 to 6 do,条件1 and 条件2,y,n,In(temp),Temp=goal,y,n,Print 打印,Exit 退出,Until head=tail,11,翻币问题。有,N,个硬币（,N=6,），正面朝上排成一排，每次将,5,个硬币翻过来放在原来位置，直到最后全部硬币翻成反面朝上为止。编程让计算机找了步数最少的翻法，并把翻币过程及次数打印出来（用,O,表示正面，表示反面）,12,综合数据库,type,node=record,r:integer;,( 由父节点翻了几个正面朝上的硬币得到当前状态),num:integer;(当前状态中硬币朝上的个数),pnt:integer;( 父节点位置),end;,Var,data:array1.1000 of node;,temp:node;,13,产生式规则:,6条，,即翻,R,个（,R=0,，,1,，,2,，,3,，,4,，,5,）正面朝上的硬币,生成结点的条件：,（1）,当前状态有多于,R,个正面朝上的硬币,M=R,（,M,表示当前结点正面朝上硬币的个数），否则出现负数,（2）,当前状态有多于,5-R,个反面朝上的硬币,N-M=5-R,（,N,表示硬币总数），例如当全部是正面时，,R,只能取,5,，不能取,04,。这时,N=M,，只有,R=5,时，不等式才成立。,（3）,当前状态已存在状态不重复,新结点正面朝上硬币个数,=,（,M-R,）,+(5-R),14,搜索策略,（BFS）,框图：,初始,head=0,Tail=0,初始化INIT;初始结点入队,结点出队out(temp1),temp temp1 change(temp),For r:=0 to 5 do,条件1 and 条件2 and not(dupe(temp),y,n,In(temp),Temp=goal,y,n,Print 打印,Exit 退出,Until head=tail,15,