Algorithm 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Algorithm
标  题: 深度优先搜索法
发信站: 哈工大紫丁香 (Wed Aug 13 16:03:47 2003)

1. 对已产生的结点按深度排序,深度大的先得到扩展,即先产生它的子结点;
2. 深度大的结点是后产生的,但先得到扩展,即“后产生先扩展”。因此用堆栈作为

该算
法的主要数据结构,存储产生的结点,先把产生的数入栈,产生站顶(即深度最大的元


素)子结点,子结点产生以后,出栈,再产生栈顶子结点。
深度优先搜索的基本算法如下:
一. 递归算法:
递归过程为:
procedure DFS_TRY(i);
For r:=1 to maxr do
If 子结点MR 符合条件 THEN
产生的子结点MR压入栈;
IF 子结点 MR是目标结点 THEN 输出
ELSE DFS_RY(I+1);
栈顶元素出栈(删去MR);
endif;
enddo;
{*********************main***************************}
program DFS;
初始状态入栈;
DFS_TRY(i);
二. 非递归算法
program DFS(dep);{UNRECIRETION}
dep:=0;
repeat
dep:=dep+1;
j:=j+1;
if mr 符合条件then
产生子结点mr并将其记录
if 子结点是目标 then 输出并出栈
else p:=true;
else
if j>maxj then 回溯 else p:=false;
endif;
until p=true;
until dep=0;
其中回溯过程如下:
procedure backtracking;
dep:=dep-1;
if dep>0 then 取回栈顶元素
else p:=true;
不同问题的深度优先搜索算法是一样的,但在具体处理方法上,编程技巧上,不尽相同


迷宫问题:
(一) 问题分析
1. 迷宫的表示方法:迷宫可以用一个二维数组A(Y,X)表示,其中,Y表示行,X
表示列。数组中的元素由数字0和1组成,当A(Y,X)=1时表示墙;当A(Y,
X)=0时表示路。
2. 搜索方向的识别:
对于迷宫中的任意一点A(Y,X),有四个搜索方向:向上A(Y-1,X);向下A
(Y+1,X);向左A(Y,X-1);向右A(Y,X+1)
3. 搜索方向的表示方法:(0,1)表示向右;(-1,0)表示向上;(0。-1)表示向

左;
(1,0)表示向下
4. 向某个方向试探一步:在搜索时一定要注意,任何一点的坐标加上搜索方向的坐标


增量后,都要判断是否超出了迷宫的边界。当不出界时,A(Y,X)=0表示该方
向为通路。
5. 当从死胡同退出时,要将路堵死,可将其标记为2。
6. 在搜索中还要建立一个堆栈,将所走过的路记录下来,后退时将退出的路从堆栈中


弹出。这样保证了最终保存的是迷宫的一条出路。栈底元素为入口坐标,栈顶元素
为迷宫的出口坐标。
(二) 产生式系统
1. 数据库。为了要存储所走过的路,每个记录要有:行,列坐标,搜索方向三个数据


而且数据库应组成堆栈形式,并用DEP作为栈顶指针,同时表示搜索深度。
2. 产生规则。共有八条,可用数组DX和DY表示方向增量:nx=x+dx(j); ny=y+dy(j)
if (nx,ny)是通路 then (nx,ny)是新结点
3. 搜索策略。由于迷宫较大,为了防止溢出应采用非递归算法。
(三) PASCAL源程序
Program labyrinth(output);
uses crt;
type node=record
xx,yy:byte;
r:byte;
end;
all=array[0..11,0..11] of byte;
const dx:array[1..4] of integer=(0,1,0,-1);
dy:array[1..4] of integer=(1,0,-1,0);
a:all=
((1,1,1,1,1,1,1,1,1,1,1,1),(1,0,0,0,0,0,0,1,0,1,1,1)),
(1,0,1,0,1,1,0,0,0,0,0,1),(1,0,1,0,1,1,0,1,1,1,0,1),
(1,0,1,0,0,0,0,0,1,0,0,1),(1,0,1,1,1,1,1,1,1,1,1,1),
(1,0,0,0,1,0,1,0,1,1,1,1),(1,0,1,1,1,0,0,0,0,0,0,1),
(1,0,0,0,0,0,1,0,1,1,0,1),(1,1,1,0,1,1,1,0,0,1,1,1),
(1,1,1,1,1,1,1,1,0,1,1,1),(1,1,1,1,1,1,1,1,1,1,1,1));
var b:all;
dep,j,k,x,y,xo,yo,nx,ny:integer;
path:array[0..300] of node;
p:boolean;
procedure wait;
begin for k:=1 to 5000 do end;
procedure display(a:all);
var i,j:byte;
begin
for i:=0 to 11 do
begin
for j:=0 to 11 do write(a[i,j]);
writeln;
end;
end;
function check :boolean;
begin
nx:=x+dx[j];
ny:=y+dy[j];
if (nx<1) or (nx>11) or (ny<1) or (ny>11)
then check:=false
else if a[ny,nx]>0 then check:=false
else check:=true;
end;
procedure backtrack;
begin
repeat
dec(dep);
if dep=0
then p:=true
else
begin
a[y,x]:=2;gotoxy(x+1,y+1);write(chr(176));wait;
x:=path[dep].xx;
y:=path[dep].yy;
j:=path[dep].r;
end;
until (dep=0) or (j<4);
end;
procedure print(dep:integer);
var i,k:integre;
ch:char;
begin
gotoxy(nx+1,ny+1);write(chr(219));
gotoxy(1,15);
write('see you again(y/n)?');readln(ch);
if (ch='y') or (ch='Y') then
begin
clrscr;display(b);
for i:=1 th dep do
with path[i] do
begin gotoxy(xx+1,yy+1);write(chr(219));
wait;
end;
gotoxy(1,20);write('end!');readln;
end;
halt;
end;
{===============main==============}
begin
yo:=10;xo:=8;
b:=a;
clrscr;display(a);
dep:=1;
with path[i] do
begin xx:=8;yy:1 end;
repeat
with path[dep] do
begin x:=xx:y:=yy end;
gotoxy(x+1,y+1);write(chr(219));
wait;
j:=0;p:=false;
repeat
inc(j);
if check then
begin a[y,x]:=1;path[dep].r:=j;
inc(dep);
with path[dep] do
begin xx:=nx;yy:=ny;end;
if (nx=xo) and (ny=yo) then print(dep)
else p:=true;
end
else
if j>=4 then backtrack;
until p=true;
until dep=0;
readln;
end.

--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝

※ 来源:.哈工大紫丁香 bbs.hit.edu.cn [FROM: 202.118.229.162]
[百宝箱] [返回首页] [上级目录] [根目录] [返回顶部] [刷新] [返回]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间:3.751毫秒