广度优先搜索.docx
《广度优先搜索.docx》由会员分享，可在线阅读，更多相关《广度优先搜索.docx（19页珍藏版）》请在冰点文库上搜索。
广度优先搜索
广度优先搜索算法
一．宽度优先搜索的过程
宽度优先搜索算法是最简便和常用的图形搜索算法之一，这一算法也是很多重要的图的算法的原型。
Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。
宽度优先算法的核心思想是：
从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。
若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。
即
1、从图中的某一顶点V0开始，先访问V0；
2、访问所有与V0相邻接的顶点V1，V2，......，Vt；
3、依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点；
4、循此以往，直至所有的顶点都被访问过为止。
5、这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。
对同一层结点来说，一般按先生成先扩展的顺序进行，因此在数据结构上引入了“队列”结构。
“队列”是一种线性表，具有先进先出的特点，对于它所有的插入和删除操作分别仅在队列尾和队列首进行。
二、广度优先搜索算法描述：
ProgramBfs；
初始化，初始状态存入OPEN表；
队列首指针head:
=0;尾指针tail:
=1；
repeat
指针head后移一位，指向待扩展结点；
forI=1tomaxdo{max为产生子结点的规则数}
begin
if子结点符合条件then
begin
tail指针增1，把新结点存入列尾；
if新结点与原已产生结点重复then删去该结点（取消入队，tail减1）
else
if新结点是目标结点then输出并退出；
end;
end;
until（tail>=head）;{队列空}
三、广度优先搜索注意事项：
1、每生成一个子结点，就要提供指向它们父亲结点的指针。
当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。
2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间，还有可能陷入死循环。
3、如果目标结点的深度与“费用”（如：
路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。
4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。
下面我们看看怎样用宽度优先搜索来解决八数码问题。
例如 图2给出广度优先搜索应用于八数码难题时所生成的搜索树。
搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。
粗线条路径表明求得的一个解。
从图中可以看出，扩展２６个结点和生成４６个结点之后，才求得这个解。
此外，直接观察此图表明，不存在有更短走步序列的解。
图2 广度优先搜索图
程序实现算法：
ProgramBFS；
建立数据库data；数据库赋初值；
设队列头指针H:
=0；队列尾指针L:
=1；
repeat
取下一个H所指的结点；
fori:
=1tomaxdo{i为产生新结点规则编号}
begin
L增1，把新结点存入数据库队尾；记录父结点的位置；
if新结点与原有结点重复then
删去该结点（L减1）
else
if新结点为目标结点then输出并退出；
end；
end；
untilH>=L{队列为空}
程序：
program8no_bfs;{八数码的宽度优先搜索算法}
Const
Dir:
array[1..4,1..2]ofinteger {四种移动方向，对应产生式规则}
=（（1,0）,（-1,0）,（0,1）,（0,-1））;
N=10000;
Type
T8No=array[1..3,1..3]ofinteger;
TList=record
Father:
integer; {父指针}
dep:
byte; {深度}
X0,Y0:
byte;{0的位置}
State:
T8No; {棋盘状态}
end;
Var
Source,Target:
T8No;
List:
array[0..10000]ofTList;{综合数据库}
Closed,Open,Best:
integer{Best表示最优移动次数}
Answer:
integer;{记录解}
Found:
Boolean;{解标志}
procedureGetInfo;{读入初始和目标节点}
vari,j:
integer;
begin
fori:
=1to3do
forj:
=1to3doread（Source[i,j]）;
fori:
=1to3do
forj:
=1to3doread（Target[i,j]）;
end;
procedureInitialize;{初始化}
varx,y:
integer;
begin
Found:
=false;
Closed:
=0;Open:
=1;
withList[1]dobegin
State:
=Source;dep:
=0;Father:
=0;
Forx:
=1to3do
Fory:
=1to3do
ifState[x,y]=0thenBeginx0:
=x;y0:
=y;End;
end;
end;
FunctionSame（A,B:
T8No）:
Boolean;{判断A,B状态是否相等}
Vari,j:
integer;
Begin
Same:
=false;
Fori:
=1to3doforj:
=1to3doifA[i,j]<>B[i,j]thenexit;
Same:
=true;
End;
functionNot_Appear（New:
tList）:
boolean;{判断New是否在List中出现，可用康托展开实现映射，建立hash表，用O
（1）的时间复杂度判重}
vari:
integer;
begin
Not_Appear:
=false;
fori:
=1toOpendoifSame（New.State,List[i].State）thenexit;
Not_Appear:
=true;
end;
procedureMove（N:
tList;d:
integer;varok:
boolean;varNew:
tList）;
{将第d条规则作用于N得到New,OK是New是否可行的标志}
varx,y:
integer;
begin
X:
=N.x0+Dir[d,1];
Y:
=N.y0+Dir[d,2];
{判断New的可行性}
Ifnot（（X>0）and（X<4）and（Y>0）and（Y<4））thenbeginok:
=false;exitend;
OK:
=true;
New.State:
=N.State;{New=Expand（N,d）}
New.State[X,Y]:
=0;
New.State[N.x0,N.y0]:
=N.State[X,Y];
New.X0:
=X;New.Y0:
=Y;
end;
procedureAdd（new:
tList）;{插入节点New}
begin
Ifnot_Appear（New）thenBegin{如果New没有在List出现}
Inc（Open）;{New加入Open表}
List[Open]:
=New;
end;
end;
procedureExpand（Index:
integer;varN:
tList）;{扩展N的子节点}
vari:
integer;
New:
tList;
OK:
boolean;
Begin
IfSame（N.State,Target）thenbegin{如果找到解}
Found:
=true;
Best:
=N.Dep;
Answer:
=Index;
Exit;
end;
Fori:
=1to4dobegin{依次使用４条规则}
Move（N,i,OK,New）;
ifnotokthencontinue;
New.Father:
=Index;
New.Dep:
=N.dep+1;
Add（New）;
end;
end;
procedureGetOutInfo;{输出}
procedureOutlook（Index:
integer）;{递归输出每一个解}
vari,j:
integer;
begin
ifIndex=0thenexit;
Outlook（List[Index].Father）;
withList[Index]do
fori:
=1to3dobegin
forj:
=1to3dowrite（State[i,j],''）;
writeln;
end;
writeln;
end;
begin
Writeln（'Total=',Best）;
Outlook（Answer）;
end;
procedureMain;{搜索主过程}
begin
Repeat
Inc（Closed）;
Expand（Closed,List[Closed]）;{扩展Closed}
Until（Closed>=Open）orFound;
IfFoundthenGetOutInfo{存在解}
elseWriteln（'Noanswer'）;{无解}
end;
Begin
Assign（Input,'input.txt'）;ReSet（Input）;
Assign（Output,'Output.txt'）;ReWrite（Output）;
GetInfo;
Initialize;
Main;
Close（Input）;Close（Output）;
End.
例1在一个瓶中装有80毫升化学溶剂，实验中需要精确地平分成两份，没有量具，只有两个杯子，其中一个杯子的容量是50毫升，另一个是30毫升，试设计一个程序将化学溶剂对分成两个40毫升，并以最少步骤给出答案。
（文件名：
EX1.PAS）
输出（EX1.OUT）：
Start:
8000
StepNo.1:
30500
StepNo.2:
302030
StepNo.3:
60200
StepNo.4:
60020
StepNo.5:
105020
StepNo.6:
104030
StepNo.7:
40400
End.
分析:
三个杯子水的初始状态为:
８０、０、０，生成新结点状态的方法为：
将一个不空的杯子水倒入一个不满的杯中，且结点状态不重复，直到生成目标结点为止。
算法步骤:
1、数据库:
用数组d构成存放生成结点（杯子水状态）的队；数组p作为指向父结点的指针；t和s作为队头与队尾指针。
2、结点的产生:
（1）将结点中不空的杯子水倒入一个不满的杯子中，生成新的结点并记下父结点位置；
（2）判断新结点是否已生成过，以避免死循环；
（3）生成的结点若为目标结点，输出。
3、搜索策略:
广度优先搜索。
源程序如下:
programex1;
type
status=array[1..3]ofinteger;
const
v:
array[1..3]ofinteger=（80,50,30）;
var
d:
array[1..200]ofstatus;
p:
array[1..200]ofinteger;
t,s,i,j:
integer;
proceduredraw（f:
integer）;{输出}
var
m:
array[1..20]ofinteger;
i,j,k:
integer;
begin
j:
=0;
whilef<>1dobegin
inc（j）;
m[j]:
=f;
f:
=p[f];
end;
writeln;
writeln（'Start:
',d[1,1]:
3,d[1,2]:
3,d[1,3]:
3）;
fori:
=jdownto1dobegin
write（'StepNo.',j+1-i,':
'）;
fork:
=1to3dowrite（d[m[i],k]:
3）;
writeln;
end;
writeln（'End.'）;
halt;
end;
functionexampass（w:
integer）:
boolean;{新结点是否以前生成过}
var
i:
integer;
begin
fori:
=1tow-1do
if（d[i,1]=d[w,1]）and（d[i,2]=d[w,2]）and（d[i,3]=d[w,3]）
thenbegin
exampass:
=false;
exit;
end;
exampass:
=true;
end;
functionisobject（w:
integer）:
boolean;{是否为目标结点}
begin
if（d[w,1]=40）and（d[w,2]=40）thenisobject:
=true
elseisobject:
=false;
end;
begin{生成新结点,将一个不空的杯子水倒入一个不满的杯子中}
assign（output,'ex1.out'）;
rewrite（output）;
d[1,1]:
=80;d[1,2]:
=0;d[1,3]:
=0;
p[1]:
=0;
t:
=1;s:
=2;
repeat
fori:
=1to3do
ifd[t,i]<>0then
forj:
=1to3do
if（i<>j）and（d[t,j]<>v[j]）thenbegin
d[s]:
=d[t];
d[s,j]:
=d[s,j]+d[s,i];
d[s,i]:
=0;
ifd[s,j]>v[j]thenbegin
d[s,i]:
=d[s,j]-v[j];
d[s,j]:
=v[j];
end;
p[s]:
=t;
ifexampass（s）thenbegin
ifisobject（s）thendraw（s）;
inc（s）;
end;
end;
inc（t）;
untilt>=s;
writeln（'NoWay'）;
close（output）;
end.
例2跳棋的原始状态如下图。
其中"0"表示空格，"-"表示白子，"+"表示黑子，"1--7"表示棋盘格编号。
跳棋的规则是：
⒈任意一个棋子可移到相邻的空位上；
⒉可跳过一个或两个棋子到空位上，与跳过的棋子的颜色无关；
⒊棋子向左向右跳不限。
例如：
4到1、5到4、3到5、6到3是成功的四步走法。
请编一程序，用10步完成从原始状态跳变成目标状态。
要求打印跳每一步后的状态。
用数字表示棋盘格子的代号。
1234567
原始位置0---+++
目标位置+++---0
分析:
此题可以用广度与深度搜索两种方法求解，通过运行两种解法的程序，我们可以粗略地知道两种算法的区别。
算法步骤:
⒈数据库：
数组ｇ构成队，存放棋子的状态；数组ｐ作为指针指向其父结点位置；ｔ与ｓ分别表示队头与队尾指针。
⒉结点的产生：
与位置间距-3到3的棋子可移入空位，生成新结点状态。
⒊搜索策略：
广度优先搜索。
源程序如下:
programex143-1;{广度优先搜索}
usestime;
type
status=string[7];
const
start:
status='0---+++';
obj:
status='+++---0';
var
a,b,c:
timetype;
g:
array[1..200]ofstatus;
p:
array[1..200]ofinteger;
i,j,k:
integer;
t,s:
integer;
proceduredraw（f:
integer）;{输出}
var
m:
array[1..10]ofinteger;
i,j:
integer;
begin
j:
=0;
whilef<>1dobegin
inc（j）;
m[j]:
=f;
f:
=p[f];
end;
writeln;
writeln（'Start:
',start）;
fori:
=jdownto1do
writeln（'StepNo.',j+1-i,':
',g[m[i]]）;
writeln（'End'）;
gettimenow（b）;
howlong（a,b,c）;
printtime（'TimeTake:
',c）;
halt;
end;
functionexampass（w:
integer）:
boolean;{判断结点有否重复}
var
i:
integer;
begin
fori:
=1tow-1do
ifg[i]=g[w]thenbegin
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]）;
fori:
=-3to3do
if（i<>0）and（k+i>=1）and（k+i<=7）thenbegin
g[s]:
=g[t];
g[s,k]:
=g[s,k+i];g[s,k+i]:
='0';
p[s]:
=t;
ifexampass（s）thenbegin
ifg[s]=objthendraw（s）;
inc（s）;
end;
end;
inc（t）;
untilt>=s;
writeln（'NoWay'）;
end.
算法
（二）:
1、数据库：
数组ｇ构成堆栈，存放棋子的状态。
2、结点的产生：
与空位置间距－３到３的棋子可移入空位，生成新结点状态。
3、搜索策略：
含有深度界限的深度优先搜索。
源程序如下:
programex143-2;{深度优先搜索}
usestime;
type
status=string[7];
const
start:
status='0---+++';
obj:
status='+++---0';
var
a,b,c:
timetype;
g:
array[0..10]ofstatus;
i,j,k:
integer;
proceduredraw;{输出}
var
i,j:
integer;
begin
writeln（'Start:
',start）;
fori:
=1to10do
writeln（'StepNo.',i,':
',g[i]）;
writeln（'End'）;
gettimenow（b）;
howlong（a,b,c）;
printtime（'TakeTime:
',c）;
halt;
end;
functionexampass（w:
integer）:
boolean;{判断有否重复状态}
var
i:
integer;
begin
fori:
=1tow-1do
ifg[i]=g[w]thenbegin
exampass:
=false;
exit;
end;
exampass:
=true;
end;
procedurerun（t:
integer）;{搜索生成新结点}
var
i,k:
integer;
begin
k:
=pos（'0',g[t-1]）;
fori:
=-3to3do
if（i<>0）and（k+i>=1）and（k+i<=7）thenbegin
g[t]:
=g[t-1];
g[t,k]:
=g[t,k+i];g[t,k+i]:
='0';
ifexampass（t）then
ifg[t]=objthendraw
else
ift<10thenrun（t+1）;
end;
end;
begin
gettimenow（a）;
g[0]:
=start;
run
（1）;
end.
运行两种算法程序可以发现，广度优先搜索运行速度比深度优先搜索快。
那么深度优先搜索与广度优先搜索算法有何区别呢？
通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。
所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。
广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。
但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。
升级会员 