广度优先搜索实例

1、广度优先搜索 实例【例题】八数码难题 （Eight-puzzle） 。在 3X3 的棋盘上，摆有 8 个棋子，在每个棋子上标有18中的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的 问题是， 给出一种初始布局 （ 初始状态 ） 和目标布局 （ 目标状态 ） ，找到一种最少步骤的移动方 法，实现从初始布局到目标布局的转变。初始状态和目标状态如下：初始状态 目标状态 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5求解本题我们可以分 3 步进行。问题分析 ： 由的解于题目要找是达到目标的最少步骤，因此可以这样来设计解题的方法： 初始状态为搜索的出发点，把移动一步

2、后的布局全部找到，检查是否有达到目标的布局，如 果没有，再从这些移动一步的布局出发，找出移动两步后的所有布局，再判断是否有达到目 标的。依此类推，一直到某布局为目标状态为止，输出结果。由于是按移动步数从少到多产 生新布局的，所以找到的第一个目标一定是移动步数最少的一个，也就是最优解。建立产生式系统 ：（1）综合数据库。用 3X3 的二维数组来表示棋盘的布局比较直观。我们用Chi,j 表示第 i行第 j 列格子上放的棋子数字， 空格则用 0 来表示。 为了编程方便， 还需存储下面 3 个数据： 该布局的空格位置（Si , Sj）；初始布局到该布局的步数，即深度 dep ；以及该布局的上一布 局，

3、即父结点的位置 （pnt） 。这样数据库每一个元素应该是由上述几个数据组成的记录。 在程序中，定义组成数据库元素的记录型为：Typenode = recordch： array 1 .3 ， 1.3 of byte； 存放某种棋盘布局 si,sj:byte ； 记录此布局中空格位置 dep,pnt ： byte ；end；因为新产生的结点深度 （从初始布局到该结点的步数 ）一般要比数据库中原有的结点深度大（或相等） 。按广度优先搜索的算法，深度大 （步数多 ）的结点后扩展，所以新产生的结点应放 在数据库的后面。 而当前扩展的结点从数据库前面选取， 即处理时是按结点产生的先后次序 进行扩展。这样

4、广度优先搜索的数据库结构采用队列的结构形式较合适。我们用记录数组 data 来表示数据库，并设置两个指针： Head 为队列的首指针， tail 为队列的尾指针。（2）产生规则。原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察，也可 看作空格向上、下、左、右 4 个位置移动，这样处理更便于编程。设空格位置在 （Si ， sj） ， 则有 4 条规则： 空格向上移动： if si-1>=1 then chsi,sj:=chsi-1,sj； chsi-1,sj:=0空格向下移动： if si+1<=3 then si,sj:=chsi+1,sj； chsi+1,sj:=0

5、空格向左移动：if sj-1<=1 then si,sj:=chsi,sj-1； chsi,sj-1:=0 空格向右移动：if sj+1<=3 then si,sj:=chsi,sj+1； chsi,sj+1:=0我们用数组 Di和Dj来表示移动时行列的增量，移动后新空格的位置可表示为：n x:=si+di(r)ny:=sj+dj(r)其中，r=1,2,3,4为空格移动方向，且r 1 2 3 4 方向 左 上右下di 0 -1 0 1 dj -1 01 0(3) 搜索策略。按照问题分析中提岀的方法，算法设计如下:初始化;把初始布局存人数据库血山;设首措针Head：二0；尾指针丁时:

6、=1；队列首记录为当前被扩展结点;FOR r： = l TO 4 DO【r是规则编号新空格位罟合法 -一一一一一 / ?T曲増lr并把新布局徉人队尾：；f新审局与队列中原有记录里复一十"删除新产生的布局达到目标T "输岀并退出；Until H爾dA-Tail； 队列空program num8 ；程序中新布局与队列中已有布局是否重复，用dup函数检查；找到目标结点后， print过程负责打印岀从初始态到目标态移动时各步的布局，bufn)是用来存放待输岀的布局在队列中的位置。function dup: boolean ；but： = false；i： - 0i 増1 buf ：

7、 = true；_” 一TfIfinl chLj 1 k <Lim I.chj、kl-"-'j一buf： = truebuf： = falseunxiibuf Or (I> = rail- l )dupe：=:buf；procedure printn* = 1； i： = tail；: = tail记录结点i的父结点位置 j： =dataL I. pnt 口增1;修改I值，使其指向原结点的父结点位置Umil找到根结点11 = 0!打印从根结点到目标结点路径上各种布局停止根据上述算法编制的程序如下:program n um8_str1 ；uses Crt ；type

8、 a33 ： array1.3 ， 1.3 Of byte；3X3 的二维数组，用于存放棋盘布局 a4=array1.4 of shortint;node=record 定义数据库中每个元素记录类型结构 ch: a33;si, sj: byte;pnt, dep: byte; end;const goal:a33 = (1,2,3), (8,0,4), (7,6,5); start:a33 =(2,8,3), (1,6,4), (7,0,5); 目标布局 初始布局 di:a4=(0,-1, 0, 1); dj:a4=(-1, 0, 1, 0);var data:array1.100 of no

9、de;temp: node;r, k, ni, nj, Head, Tail, depth: integer; 变量 depth 存放当前搜索深度 function check(k: integer) :boolean; beginhi:=temp.si+dik ; nj:=temp.sj+djk; if (ni in 1.3) and (nj in 1.3) 检查某步移动是否可行移动后新位置仍在棋盘中then check:=true else check:= false; end;function dupe: boolean; 检查队尾新存入布局是否已在队列中存在var i,j, k: in

10、teger; buf:boolean;Beginbuf:= false; i: = 0; 变量将 i 依次指向队列中的各个布局 ( 最后一个除外 ) 的位置 repeatinc(i) ;buf:= true;for j:=1 to 3 do for k:=1 to 3 doif datai.chj,k < >datatail.chj,kdatatail 是队列中最后一个元素，即新产生的布局 then bur:= false;until buf or (i> = tail-1);buf=truee 新布局与队列中布局有重复 dupe:= buf比较是否达到目标布局状态 end;

11、function goals: boolean; var i,j :byte;begin goals:= true;for i:=1 to 3 do for j:=1 to 3 do if datatail.chi,j < >goa1i,j then goals:=false 未达到目标布局 end;procedure trace; var i,j :byte;begin write( 'cl=', Head,' op=', tail); writeln('dep=',depth,'k=',k);fori:=1 to

12、3 do begin for j:= 1 to 3 do write(datatail, chi,j); writeln end;end; procedure print; 输出移动步骤 var buf: array1.100 of integer; 数组 buf 存放起始态、目标态以及从起始态到目标态所经过的各态的位置 i,j, k, n: integer;begin n:= 1;i:= tail;buf1:= i; buf1 中是目标布局在队列中位置 repeatj:=datai.pnt; dataI.pnt 的值是布局 I 的父结点的位置 inc(n); bufn:=j; i:=junt

13、il i=0; 根结点 ( 初态 ) 的父结点为 0，即 I=0writeln(' staps:', depth + 1);for i:= 1 to 3 do 打印棋盘布局 beginfor k:=n-1 down to 1 dobegin for j:= 1 to 3 do write(databufk.chi,j); if i = 2 then write( ' - > ') else write(' ');end; writeln;end;readln; haltend; main program = beginHead:= 0; t

14、ail:= 1;with data1 do 队列中存入第一个元素 ( 初始状态 )begin ch:= start; si:= 3; sj:= 2;pnt:= 0; dep:= 0;end;repeat inc(Head);temp:=dataHead; 取队首记录 depth:= temp.dep;for r:= 1 to 4 do 对取出记录进行扩展 if check(r) then 布局中空格向某方向移动成功 begininc(tail);datatail:= temp; 新产生布局存入队尾 with datatail dobegin chsi,si:= chnj,nj; chni,nj

15、:=0;si:=nj;si:=nj;pnt:=Head; 记录此布局的上一布局在队列中的位置 dep:= depth + 1; 记录本布局的搜索深度 end;trace;if dupe then dec(tail) dec(tail 删除新产生的结点 ) else if goals then print;end;until Head>=tail; 队列空 writeln('no solution');readln end运行结果：283 283 283 023 123 123164>104>184 >184 >084 >804705 765

16、765 765 765 765 上述程序产生的搜索各个布局图略。从上面搜索图中可看出， 程序执行时先产生深度为 1 的所有结点， 然后再产生深度为 2 的所 有结点, ，最后产生含有目标的深度为 5 的结点结束。先往横向扩展，再往纵向深入，这 就是广度优先搜索法搜索过程。从上例我们看出，广度优先搜索法可以求出步数最少的解，即深度最少的解。因此广度优先 搜索法经常用于一些求最优解的问题中。与深度优先搜索法类似， 不同的问题用广度优先搜索法的基本算法都是一样的， 但在数据库 的表示方法上、 在产生的结点是否符合条件上和重复的判断上可以有不同的编程技巧， 程序 运行效率也会有所不同。 以八数码问题为例， 上面程序中用 3X3 的二维数组表示布局比较直 观，但在判断有重复布局，判断是否达到目标布局方面，却增加了编程复杂性，同时也影响 了运行速度。我们可以改用字符串形式来表示布局。例如初始布局表示为 "283164705'' ，目 标布局表示为“ 123804765”，即按行的顺序排列产生规则也必须作相应改动。设空格当前位置是 Si ，则有：(1) 空格向上移动：空格的位置减(2) 空格向左移动：空格的位置减(3) 空格向右移动：空格的