广度优先搜索算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,广度优先搜索算法,例 八数码难题。,在33,的棋盘上，摆 有八个棋子，每个棋子上标有,1至8,的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始布局初始状态和目标布局目标状态，找到一种移动的方法，实现从初始布局到目标布局的转变。,2 8 3,1 6 4,7 5,1 2 3,8 4,7 6 5,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, ,综合数据库,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条，空格向上，下，左，右四个方向移动,生成结点的条件：,（1）新状态不出界,（2）和已生成结点不重复,ni,:=temp.,si,+,di,k;,nj,:=temp.,sj,+,dj,k;,with temp do,begin,ch,si,sj,:=,ch,ni,nj,;,ch,ni,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,搜索策略,（,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,练习：,有两个无刻度标志的水壶，分别可装,5,升水和,2,升水，设另有一水缸，可用来向水壶灌水或倒出水，两水壶间，水也可以相互倾灌。已知,5,升壶为满壶，,2,升壶为空壶。问如何通过倒水或灌水操作，用最少步数能在,2,升壶中量出,1,升水来。编一程序解决问题。,如图是六个城市之间道路联系的示意图，连线表示两城市间有道路相通，连线旁的数字表示路程。请编程序，由计算机找到从,C1,到,C6,的一条路径及路程总长度，要求求出经过城市最少的解和路程总长度最少的解。,C6,3,4,4,8,4,9,2,2,6,4,C1,C2,C5,C4,C3,综合数据库,type,node=record,city:integer;,城市编号,flag:set of 1.6;,到根结点的路径,pnt,:integer;,父节点,end;,Var,data:array1.1000 of node;,temp:node;,产生式规则:,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;,搜索策略,（,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,翻币问题。有,N,个硬币（,N=6,），,正面朝上排成一排，每次将,5,个硬币翻过来放在原来位置，直到最后全部硬币翻成反面朝上为止。编程让计算机找了步数最少的翻法，并把翻币过程及次数打印出来（用,O,表示正面，表示反面）,综合数据库,type,node=record,r:integer;,(,由父节点翻了几个正面朝上的硬币得到当前状态),num:integer;(,当前状态中硬币朝上的个数),pnt,:integer;(,父节点位置),end;,Var,data:array1.1000 of node;,temp:node;,产生式规则:,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),搜索策略,（,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,