中国教育曙光网-奥赛

趣谈数据结构（十二）

　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　 福州一中陈颖
　　
　　本讲对广度优先搜索算法的应用作进一步的讨论。
　　用广度优先搜索解题时，结点的扩展（ＯＰＥＮ）表是一个队即先进先出的顺序表，每次取队头的结点进行扩展，新扩展的结点加入队尾，直到搜索到目标结点或队空为止。

　　具体算法：
　　⒈把起始结点放入OPEN表中(先进先出的顺序表)，如果该起始结点为一目标结点，则求得一个解答。
　　⒉如果OPEN是个空表，则搜索失败退出，否则继续。
　　⒊取OPEN表中最前面(队头)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号ｎ。
　　⒋扩展结点ｎ。如果没有后继结点，则转向上述第２步。
　　⒌把ｎ的所有后继结点放到OPEN表的末端(队尾)，并提供从这些后继结点回到ｎ的指针。
　　⒍如果ｎ的任一个后继结点是个目标结点，则找到一个解答，成功退出；否则转向第２步。

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

　　　　　　　　　　　　　　　　　　　图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.
　　运行两种算法程序可以发现，广度优先搜索运行速度比深度优先搜索快。
　　那么深度优先搜索与广度优先搜索算法有何区别呢？
　　通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。
　　广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。

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


网站导航 \| 关于曙光 \| 联系我们 \| 请提意见 Copyright © FuJian Sunshine Educational Info. Co.,Ltd. 福建曙光教育资讯有限公司版权所有