文档介绍：深度优先搜索的过程
深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中,对于最新发现的节点,如果它还有以此为起点而未搜索的边,就沿此边继续搜索下去。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v有那条边的始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被发现为止。即
⒈以给定的某个顶点V0为起始点,访问该顶点;
⒉选取一个与顶点V0相邻接且未被访问过的顶点V1,用V1作为新的起始点,重复上述过程;
⒊当到达一个其所有邻接的顶点都已被访问过的顶点Vi时,就退回到新近被访问过的顶点Vi- 1,继续访问Vi-1尚未访问的邻接点,重复上述搜索过程;
⒋直到从任意一个已访问过的顶点出发,再也找不到未被访问过的顶点为止,遍历便告完成。
这种搜索的次序体现了向纵深发展的趋势,所以称之为深度优先搜索。
深度优先搜索算法描述:
程序实现有两种方式--递归与非递归。
一、递归
递归过程为:
Procedure DEF-GO(step)
for i:=1 to max do
if 子结点符合条件 then
产生新的子结点入栈;
if 子结点是目标结点 then 输出
else DEF-GO(step+1);
栈顶结点出栈;
endif;
enddo;
主程序为:
Program DFS;
初始状态入栈;
DEF-GO(1);
二、非递归
Program DEF(step);
step:=0;
repeat
step:=step+1; j:=0;p:=false
repeat
j:=j+1;
if 结点符合条件 then
产生子结点入栈;
if 子结点是目标结点 then 输出
else p:=true;
else
if j>=max then 回溯 p:=false;
endif;
until p=true;
until step=0;
回溯过程如下:
Procedure BACK;
step:=step-1;
if step>0 then 栈顶结点出栈
else p:=true;
例如八数码难题--已知8个数的起始状态如图1(a),要得到目标状态为图1(b)。
2 8 3 1 2 3
1 6 4 8 ■ 4
7 ■ 5 7 6 5
(a) (b)
求解时,首先要生成一棵结点的搜索树,按照深度优先搜索算法,我们可以生成图1的搜索树。图中,所有结点都用相应的数据库来标记,并按照结点扩展的顺序加以编号。其中,我们设置深度界限为5。粗线条路径表示求得的一个解。从图中可见,深度优先搜索过程是沿着一条路径进行下去,直到深度界限为止,回溯一步,再继续往下搜索,直到找到目标状态或OPEN表为空为止。
图1 深度优先搜索图
程序:
program No8_DFS; {八数码的深度优先搜索算法}
Const
Dir : array[1..4,1..2]of integer = ((1,0),(-1,0),(0,1),(0,-1));
maxN = 15; {可以承受的最大深度}
Type
T8No = array[1..3,1..3]of integer;
tList = record
state : T8No;
x0,y0 : integer;
end;
Var
Source,Target : T8No;
List,Save : array[0..maxN]of tList; {综合数据库,最优解路径}
Open,Best : integer;
procedure GetInfo; {见程序1}
Function Same(A,B : T8No):Boolean; {见程序1}
function Not_Appear(New : tList):boolean; {见程序1}
procedure Move(N : tList;d : integer;var ok : boolean;var New : tList);
{见程序1}
procedure GetOutInfo; {输出}
var i,x,y : integer;
begin
writeln('total = ',best);
for i:=1 to best+1 do begin
for x:=1 to 3 do begin
for y:=1 to 3 do write(Save[i].