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]