《广度优先搜索算法》由会员分享，可在线阅读，更多相关《广度优先搜索算法（15页珍藏版）》请在金锄头文库上搜索。
1、广度优先搜索算法例 八数码难题。在33的棋盘上，摆 有八个棋子，每个棋子上标有1至 8的某一数字。棋盘中留有一个空格。空格周围的棋子 可以移到空格中。要求解的问题是，给出一种初始布局 初始状态和目标布局目标状态，找到一种移动的方 法，实现从初始布局到目标布局的转变。2 8 3 1 6 4 7 51 2 3 8 4 7 6 5283 164 705283 164 075283 164 750283 104 765283 064 175283 014 765203 184 765283 140 765283 164 750083 264 175283 604 175083 214 765283 7
2、14 065280 143 765283 145 760283 106 754283 163 754 综合数据库typenode=recordch:array13,13 of byte;si,sj:byte;空格的坐标pnt,dep:word;父节点和深度end;Vardata:array12600 of node;temp:node;产生式规则: 4条，空格向上，下，左，右四个方向移动 生成结点的条件： （1）新状态不出界 （2）和已生成结点不重复 ni:=temp.si+dik;nj:=temp.sj+djk; with temp dobeginchsi,sj:=chni,nj;chni,
3、nj:=0;si:=ni;sj:=nj;pnt:=head;dep:=dep+1;end;r1234 方向左上右下 di0-101 dj-1010搜索策略 （BFS）框图：初始 head=0 Tail=0初始化INIT;初始结点入队 结点出队out(temp1)temp temp1 change(temp)For r:=1 to 4 doCheck(temp) and not(dupe(temp)ynIn(temp)Temp=goalynPrint 打印Exit 退出Until head=tail练习：有两个无刻度标志的水壶，分别可装5升水和2升 水，设另有一水缸，可用来向水壶灌水或倒出水，两
4、水 壶间，水也可以相互倾灌。已知5升壶为满壶，2升壶为 空壶。问如何通过倒水或灌水操作，用最少步数能在2 升壶中量出1升水来。编一程序解决问题。如图是六个城市之间道路联系的示意图， 连线表示两城市间有道路相通，连线旁的 数字表示路程。请编程序，由计算机找到 从C1到C6的一条路径及路程总长度，要求 求出经过城市最少的解和路程总长度最少 的解。 C63448492264C1C2C5C4C3综合数据库typenode=recordcity:integer;城市编号flag:set of 16;到根结点的路径pnt:integer;父节点end;Vardata:array11000 of node;
5、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 条件2ynIn(temp)Temp=goaly
6、nPrint 打印Exit 退出Until head=tail翻币问题。有N个硬币（N=6），正面朝上 排成一排，每次将5个硬币翻过来放在原来 位置，直到最后全部硬币翻成反面朝上为止 。编程让计算机找了步数最少的翻法，并把 翻币过程及次数打印出来（用O表示正面， 表示反面） 综合数据库typenode=recordr:integer;( 由父节点翻了几个正面朝上的硬币得到当前状态)num:integer;(当前状态中硬币朝上的个数)pnt:integer;( 父节点位置)end;Vardata:array11000 of node;temp:node;产生式规则: 6条，即翻R个（R=0，1，
7、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)ynIn(temp)Temp=goalynPrint 打印Exit 退出Until head=tail
