广度优先搜索解题    作者:xieaotian发表于2009-06-18 14:50:17

	   

	   用广度优先搜索解题时，结点的扩展（ＯＰＥＮ）表是一个队即先进先出的顺序表，每次取队头的结点进行扩展，新扩展的结点加入队尾，直到搜索到目标结点或队空为止。



　　具体算法：

　　⒈把起始结点放入OPEN表中(先进先出的顺序表)，如果该起始结点为一目标结点，则求得一个解答。

　　⒉如果OPEN是个空表，则搜索失败退出，否则继续。

　　⒊取OPEN表中最前面(队头)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号ｎ。

　　⒋扩展结点ｎ。如果没有后继结点，则转向上述第２步。

　　⒌把ｎ的所有后继结点放到OPEN表的末端(队尾)，并提供从这些后继结点回到ｎ的指针。

　　⒍如果ｎ的任一个后继结点是个目标结点，则找到一个解答，成功退出；否则转向第２步。



　　例如　图1给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展２６个结点和生成４６个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。



[attach]730[/attach]

　　　　　　　　　　　　　　　　　　　图1　广度优先搜索图　　　　　　　　　　　　　　　　　　　　　　　

　　程序实现算法：

　　Program BFS；

　　　建立数据库data；数据库赋初值；

　　　设队列头指针H:=0；队列尾指针L:=1；

　　　repeat

　　　　取下一个H所指的结点；

　　　　for i:=1 to max do {i为产生新结点规则编号}

　　　　　begin

　　　　　L增1，把新结点存入数据库队尾；记录父结点的位置；

　　　　 　if 新结点与原有结点重复 then

　　　　　　删去该结点(L减1)

　　　　　　else

　　　　　　　if 新结点为目标结点 then 输出并退出；

　　　　　end；

　　　　end；

　　　until H>=L {队列为空}



　　例1 在一个瓶中装有80毫升化学溶剂，实验中需要精确地平分成两份，没有量具，只有两个杯子，其中一个杯子的容量是50毫升，另一个是30毫升，试设计一个程序将化学溶剂对分成两个40毫升，并以最少步骤给出答案。

　　分析:三个杯子水的初始状态为:８０、０、０，生成新结点状态的方法为：将一个不空的杯子水倒入一个不满的杯中，且结点状态不重复，直到生成目标结点为止。



　　算法步骤:

　　⒈数据库: 用数组d构成存放生成结点(杯子水状态)的队；数组p作为指向父结点的指针；t和s作为队头与队尾指针。

　　⒉结点的产生:

　　(1)将结点中不空的杯子水倒入一个不满的杯子中，生成新的结点并记下父结点位置；

　　(2)判断新结点是否已生成过， 以避免死循环；

　　(3)生成的结点若为目标结点，输出。

　　⒊搜索策略: 广度优先搜索。



　　源程序如下:

program ex3;

type

　status= array [1..3] of integer;

const

　v: array [1..3] of integer =(80，50,30);

var

　d: array [1..200] of status;

　p: array [1..200] of integer;

　t,s,i,j: integer;

procedure draw(f: integer);{输出}

var

　m: array [1..20] of integer;

　i,j,k: integer;

begin

　j:=0;

　while f<>1 do begin

　　inc(j);

　　m[j]:=f;

　　f:=p[f];

　end;

　writeln;

　writeln('Start: ',d[1,1]:3,d[1,2]:3,d[1,3]:3);

　for i:=j downto 1 do begin

　　write('Step No.',j+1-i,': ');

　　for k:=1 to 3 do write(d[m[i],k]:3);

　　writeln;

　end;

　writeln('End.');

　halt;

end;

function exampass(w: integer): boolean;{新结点是否以前生成过}

var

　i: integer;

begin

　for i:=1 to w-1 do

　　if (d[i,1]=d[w,1]) and (d[i,2]=d[w,2]) and (d[i,3]=d[w,3])

　　then begin

　　　exampass:=false;

　　　exit;

　　end;

　exampass:=true;

end;

function isobject(w: integer): boolean;{是否为目标结点}

begin

　if (d[w,1]=40) and (d[w,2]=40) then isobject:=true

　else isobject:=false;

end;

begin {生成新结点,将一个不空的杯子水倒入一个不满的杯子中}

　d[1,1]:=80; d[1,2]:=0; d[1,3]:=0;

　p[1]:=0;

　t:=1; s:=2;

　repeat

　　for i:=1 to 3 do

　　　if d[t,i]<>0 then

　　　　for j:=1 to 3 do

　　　　　if (i<>j) and (d[t,j]<>v[j]) then begin

　　　　　　d[s]:=d[t];

　　　　　　d[s,j]:=d[s,j]+d[s,i];

　　　　　　d[s,i]:=0;

　　　　　　if d[s,j]>v[j] then begin

　　　　　　　d[s,i]:=d[s,j]-v[j];

　　　　　　　d[s,j]:=v[j];

　　　　　　end;

　　　　　　p[s]:=t;

　　　　　　if exampass(s) then begin

　　　　　　　if isobject(s) then draw(s);

　　　　　　　inc(s);

　　　　　　end;

　　　　　end;

　　　inc(t);

　until t>=s;

　writeln('NoWay');

end.



　　例2 跳棋的原始状态如下图。其中"0"表示空格，"-"表示白子，"+"表示黑子，"1--7"表示棋盘格编号。跳棋的规则是：

　　⒈任意一个棋子可移到相邻的空位上；

　　⒉可跳过一个或两个棋子到空位上，与跳过的棋子的颜色无关；

　　⒊棋子向左向右跳不限。

　　例如：4到1、5到4、3到5、6到3是成功的四步走法。请编一程序，用10步完成从原始状态跳变成目标状态。要求打印跳每一步后的状态。用数字表示棋盘格子的代号。

　　　　　　 　　　　1 2 3 4 5 6 7

　　　　　　原始位置 0 - - - + + +

　　　　　　目标位置 + + + - - - 0

　　分析:此题可以用广度与深度搜索两种方法求解，通过运行两种解法的程序，我们可以粗略地知道两种算法的区别。　



　　算法步骤:

　　⒈数据库：数组ｇ构成队，存放棋子的状态；数组ｐ作为指针指向其父结点位置；ｔ与ｓ分别表示队头与队尾指针。

　　⒉结点的产生：与位置间距-3到3的棋子可移入空位，生成新结点状态。

　　⒊搜索策略：广度优先搜索。



　　源程序如下:

program ex143-1;

uses time;

type

　status=string[7];

const

　start: status ='0---+++';

　obj: status ='+++---0';

var

　a,b,c: timetype;

　g: array [1..200] of status;

　p: array [1..200] of integer;

　i,j,k: integer;

　t,s: integer;

procedure draw(f: integer);{输出}

var

　m: array [1..10] of integer;

　i,j: integer;

begin

　j:=0;

　while f<>1 do begin

　　inc(j);

　　m[j]:=f;

　　f:=p[f];

　end;

　writeln;

　writeln('Start: ',start);

　for i:=j downto 1 do

　　writeln('Step No.',j+1-i,': ',g[m[i]]);

　writeln('End');

　gettimenow(b);

　howlong(a,b,c);

　printtime('Time Take: ',c);

　halt;

end;

function exampass(w: integer): boolean;{判断结点有否重复}

var

　i: integer;

begin

　for i:=1 to w-1 do

　　if g[i]=g[w] then begin

　　　exampass:=false;

　　　exit;

　　end;

　exampass:=true;

end;

begin {生成新结点}

　gettimenow(a);

　g[1]:=start; p[1]:=0;

　t:=1; s:=2;

　repeat

　　k:=pos('0',g[t]);

　　for i:=-3 to 3 do

　　　if (i<>0) and (k+i>=1) and (k+i<=7) then begin

　　　　g[s]:=g[t];

　　　　g[s,k]:=g[s,k+i]; g[s,k+i]:='0';

　　　　p[s]:=t;

　　　　if exampass(s) then begin

　　　　　if g[s]=obj then draw(s);

　　　　　inc(s);

　　　　end;

　　　end;

　　inc(t);

　until t>=s;

　writeln('NoWay');

end.

　　算法步骤(二):

　　⒈数据库：数组ｇ构成堆栈，存放棋子的状态。

　　⒉结点的产生：与空位置间距－３到３的棋子可移入空位，生成新结点状态。

　　⒊搜索策略：含有深度界限的深度优先搜索。



　　源程序如下:

program ex143-2;

uses time;

type

　status=string[7];

const

　start: status ='0---+++';

　obj: status ='+++---0';

var

　a,b,c: timetype;

　g: array [0..10] of status;

　i,j,k: integer;

procedure draw;{输出}

var

　i,j: integer;

begin

　writeln('Start: ',start);

　for i:=1 to 10 do

　　writeln('Step No.',i,': ',g[i]);

　writeln('End');

　gettimenow(b);

　howlong(a,b,c);

　printtime('Take Time: ',c);

　halt;

end;

function exampass(w: integer): boolean;{判断有否重复状态}

var

　i: integer;

begin

　for i:=1 to w-1 do

　　if g[i]=g[w] then begin

　　　exampass:=false;

　　　exit;

　　end;

　exampass:=true;

end;

procedure run(t: integer);{搜索生成新结点}

var

　i,k: integer;

begin

　k:=pos('0',g[t-1]);

　for i:=-3 to 3 do

　　if (i<>0) and (k+i>=1) and (k+i<=7) then begin

　　　g[t]:=g[t-1];

　　　g[t,k]:=g[t,k+i]; g[t,k+i]:='0';

　　　if exampass(t) then

　　　　if g[t]=obj then draw

　　　　else

　　　　if t<10 then run(t+1);

　　end;

end;

begin

　gettimenow(a);

　g[0]:=start;

　run(1);

end.

　　运行两种算法程序可以发现，广度优先搜索运行速度比深度优先搜索快。

　　那么深度优先搜索与广度优先搜索算法有何区别呢？

　　通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。

　　广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。



　　到这里为此，我们的趣谈数据结构暂告一段落，欢迎指出文章中的不足之处。

【教程简介】

广度优先搜索解题


	   附件下载