广度优先搜索算法.ppt

广度优先搜索算法,例 八数码难题。,在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:array13,13 of byte; si,sj:byte;空格的坐标 pnt,dep:word;父节点和深度 end; Var data:array12600 of node; temp:node;,产生式规则: 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;,搜索策略 （BFS） 框图： 初始 head=0 Tail=0,练习： 有两个无刻度标志的水壶，分别可装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 16;到根结点的路径 pnt:integer;父节点 end; Var data:array11000 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:array11000 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