广度优先搜索算法PPT课件

.,1,广度优先搜索算法,.,2,例八数码难题。,在33的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始布局初始状态和目标布局目标状态，找到一种移动的方法，实现从初始布局到目标布局的转变。,28316475,12384765,.,3,283164705,283164075,283164750,283104765,283064175,283014765,203184765,283140765,283164750,083264175,283604175,083214765,283714065,280143765,283145760,283106754,283163754,.,4,综合数据库,typenode=recordch:array1.3,1.3ofbyte;si,sj:byte;空格的坐标pnt,dep:word;父节点和深度end;Vardata:array1.2600ofnode;temp:node;,.,5,产生式规则:4条，空格向上，下，左，右四个方向移动生成结点的条件：（1）新状态不出界（2）和已生成结点不重复ni:=temp.si+dik;nj:=temp.sj+djk;withtempdobeginchsi,sj:=chni,nj;chni,nj:=0;si:=ni;sj:=nj;pnt:=head;dep:=dep+1;end;,.,6,搜索策略（BFS）框图：初始head=0Tail=0,.,7,练习：有两个无刻度标志的水壶，分别可装5升水和2升水，设另有一水缸，可用来向水壶灌水或倒出水，两水壶间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶。问如何通过倒水或灌水操作，用最少步数能在2升壶中量出1升水来。编一程序解决问题。,.,8,如图是六个城市之间道路联系的示意图，连线表示两城市间有道路相通，连线旁的数字表示路程。请编程序，由计算机找到从C1到C6的一条路径及路程总长度，要求求出经过城市最少的解和路程总长度最少的解。,C6,3,4,4,8,4,9,2,2,6,4,C1,C2,C5,C4,C3,.,9,综合数据库,typenode=recordcity:integer;城市编号flag:setof1.6;到根结点的路径pnt:integer;父节点end;Vardata:array1.1000ofnode;temp:node;,.,10,产生式规则:5条，向R（R=2-6）城市移动生成结点的条件：（1）城市R不在已走路径中（not(Rindatahead.flag)）（2）当前城市到R有路（linkx,r0）Datatemp.city:=R;Datatemp.flag:=Datatemp.flag+R;Datatemp.pnt:=head;,.,11,搜索策略（BFS）框图：初始head=0Tail=0,初始化INIT;初始结点入队,结点出队out(temp),temp1tempchange(temp),Forr:=2to6do,条件1and条件2,y,n,In(temp),Temp=goal,y,n,Print打印,Exit退出,Untilhead=tail,.,12,翻币问题。有N个硬币（N=6），正面朝上排成一排，每次将5个硬币翻过来放在原来位置，直到最后全部硬币翻成反面朝上为止。编程让计算机找了步数最少的翻法，并把翻币过程及次数打印出来（用O表示正面，表示反面）,.,13,综合数据库,typenode=recordr:integer;(由父节点翻了几个正面朝上的硬币得到当前状态)num:integer;(当前状态中硬币朝上的个数)pnt:integer;(父节点位置)end;Vardata:array1.1000ofnode;temp:node;,.,14,产生式规则: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),.,15,搜索策略（BFS）框图：初始head=0Tail=0,初始化INIT;初始结点入队,结点出队out(temp1),temptemp1change(tem