广度优先搜索Word格式.docx
- 文档编号:7007953
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:19
- 大小:34.78KB
广度优先搜索Word格式.docx
《广度优先搜索Word格式.docx》由会员分享,可在线阅读,更多相关《广度优先搜索Word格式.docx(19页珍藏版)》请在冰点文库上搜索。
程序实现算法:
ProgramBFS;
建立数据库data;
数据库赋初值;
设队列头指针H:
=0;
队列尾指针L:
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:
{0的位置}
State:
T8No;
{棋盘状态}
Var
Source,Target:
List:
array[0..10000]ofTList;
{综合数据库}
Closed,Open,Best:
integer{Best表示最优移动次数}
Answer:
{记录解}
Found:
Boolean;
{解标志}
procedureGetInfo;
{读入初始和目标节点}
vari,j:
fori:
=1to3do
forj:
=1to3doread(Source[i,j]);
=1to3doread(Target[i,j]);
procedureInitialize;
{初始化}
varx,y:
Found:
=false;
Closed:
Open:
=1;
withList[1]dobegin
State:
=Source;
dep:
Father:
Forx:
Fory:
ifState[x,y]=0thenBeginx0:
=x;
y0:
=y;
End;
FunctionSame(A,B:
T8No):
Boolean;
{判断A,B状态是否相等}
Vari,j:
Begin
Same:
Fori:
=1to3doforj:
=1to3doifA[i,j]<
>
B[i,j]thenexit;
=true;
functionNot_Appear(New:
tList):
boolean;
{判断New是否在List中出现,可用康托展开实现映射,建立hash表,用O
(1)的时间复杂度判重}
vari:
Not_Appear:
=1toOpendoifSame(New.State,List[i].State)thenexit;
procedureMove(N:
tList;
d:
varok:
boolean;
varNew:
tList);
{将第d条规则作用于N得到New,OK是New是否可行的标志}
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:
exitend;
OK:
New.State:
=N.State;
{New=Expand(N,d)}
New.State[X,Y]:
New.State[N.x0,N.y0]:
=N.State[X,Y];
New.X0:
=X;
New.Y0:
=Y;
procedureAdd(new:
{插入节点New}
Ifnot_Appear(New)thenBegin{如果New没有在List出现}
Inc(Open);
{New加入Open表}
List[Open]:
=New;
procedureExpand(Index:
varN:
{扩展N的子节点}
New:
OK:
IfSame(N.State,Target)thenbegin{如果找到解}
=true;
Best:
=N.Dep;
Answer:
=Index;
Exit;
Fori:
=1to4dobegin{依次使用4条规则}
Move(N,i,OK,New);
ifnotokthencontinue;
New.Father:
=Index;
New.Dep:
=N.dep+1;
Add(New);
procedureGetOutInfo;
{输出}
procedureOutlook(Index:
integer);
{递归输出每一个解}
ifIndex=0thenexit;
Outlook(List[Index].Father);
withList[Index]do
=1to3dobegin
=1to3dowrite(State[i,j],'
'
);
writeln;
Writeln('
Total='
Best);
Outlook(Answer);
procedureMain;
{搜索主过程}
Repeat
Inc(Closed);
Expand(Closed,List[Closed]);
{扩展Closed}
Until(Closed>
=Open)orFound;
IfFoundthenGetOutInfo{存在解}
elseWriteln('
Noanswer'
{无解}
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
分析:
三个杯子水的初始状态为:
80、0、0,生成新结点状态的方法为:
将一个不空的杯子水倒入一个不满的杯中,且结点状态不重复,直到生成目标结点为止。
算法步骤:
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:
proceduredraw(f:
{输出}
m:
array[1..20]ofinteger;
i,j,k:
begin
j:
whilef<
1dobegin
inc(j);
m[j]:
=f;
f:
=p[f];
writeln('
d[1,1]:
3,d[1,2]:
3,d[1,3]:
3);
=jdownto1dobegin
write('
StepNo.'
j+1-i,'
:
fork:
=1to3dowrite(d[m[i],k]:
End.'
halt;
functionexampass(w:
integer):
{新结点是否以前生成过}
i:
=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:
exit;
functionisobject(w:
{是否为目标结点}
if(d[w,1]=40)and(d[w,2]=40)thenisobject:
=true
elseisobject:
begin{生成新结点,将一个不空的杯子水倒入一个不满的杯子中}
assign(output,'
ex1.out'
rewrite(output);
d[1,1]:
=80;
d[1,2]:
d[1,3]:
p[1]:
t:
s:
=2;
repeat
ifd[t,i]<
0then
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]:
ifd[s,j]>
v[j]thenbegin
=d[s,j]-v[j];
=v[j];
p[s]:
=t;
ifexampass(s)thenbegin
ifisobject(s)thendraw(s);
inc(s);
inc(t);
untilt>
=s;
NoWay'
close(output);
end.
例2跳棋的原始状态如下图。
其中"
0"
表示空格,"
-"
表示白子,"
+"
表示黑子,"
1--7"
表示棋盘格编号。
跳棋的规则是:
⒈任意一个棋子可移到相邻的空位上;
⒉可跳过一个或两个棋子到空位上,与跳过的棋子的颜色无关;
⒊棋子向左向右跳不限。
例如:
4到1、5到4、3到5、6到3是成功的四步走法。
请编一程序,用10步完成从原始状态跳变成目标状态。
要求打印跳每一步后的状态。
用数字表示棋盘格子的代号。
1234567
原始位置0---+++
目标位置+++---0
分析:
此题可以用广度与深度搜索两种方法求解,通过运行两种解法的程序,我们可以粗略地知道两种算法的区别。
算法步骤:
⒈数据库:
数组g构成队,存放棋子的状态;
数组p作为指针指向其父结点位置;
t与s分别表示队头与队尾指针。
⒉结点的产生:
与位置间距-3到3的棋子可移入空位,生成新结点状态。
⒊搜索策略:
广度优先搜索。
programex143-1;
{广度优先搜索}
usestime;
status=string[7];
start:
status='
0---+++'
;
obj:
+++---0'
a,b,c:
timetype;
g:
p:
i,j,k:
t,s:
m:
array[1..10]ofinteger;
i,j:
j:
whilef<
inc(j);
m[j]:
f:
end;
writeln;
writeln('
start);
fori:
=jdownto1do
writeln('
g[m[i]]);
End'
gettimenow(b);
howlong(a,b,c);
printtime('
TimeTake:
c);
halt;
{判断结点有否重复}
i:
ifg[i]=g[w]thenbegin
exampass:
exit;
end;
exampass:
begin{生成新结点}
gettimenow(a);
g[1]:
=start;
t:
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]:
='
p[s]:
ifexampass(s)thenbegin
ifg[s]=objthendraw(s);
inc(s);
end;
end;
inc(t);
untilt>
算法
(二):
1、数据库:
数组g构成堆栈,存放棋子的状态。
2、结点的产生:
与空位置间距-3到3的棋子可移入空位,生成新结点状态。
3、搜索策略:
含有深度界限的深度优先搜索。
programex143-2;
{深度优先搜索}
array[0..10]ofstatus;
proceduredraw;
=1to10do
i,'
g[i]);
TakeTime:
{判断有否重复状态}
procedurerun(t:
{搜索生成新结点}
i,k:
k:
g[t-1]);
if(i<
g[t]:
=g[t-1];
g[t,k]:
=g[t,k+i];
g[t,k+i]:
ifexampass(t)then
ifg[t]=objthendraw
else
ift<
10thenrun(t+1);
g[0]:
run
(1);
运行两种算法程序可以发现,广度优先搜索运行速度比深度优先搜索快。
那么深度优先搜索与广度优先搜索算法有何区别呢?
通常深度优先搜索法不全部保留结点,扩展完的结点从数据库中弹出删去,这样,一般在数据库中存储的结点数就是深度值,因此它占用空间较少。
所以,当搜索树的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失为一种有效的求解方法。
广度优先搜索算法,一般需存储产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。
但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 广度 优先 搜索
![提示](https://static.bingdoc.com/images/bang_tan.gif)