深搜广搜遍历算法

《深搜广搜遍历算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、信息学资料——算法JOY深度优先搜索遍历算法深度优先搜索的过程深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的节点，如果它还有以此为起点而未搜索的边，就沿此边继续搜索下去。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v有那条边的始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被发现为止。即⒈以给定的某个顶点V0为起始点，访问该顶点；　　⒉选取一个与顶点V0相邻接且未被访问过的顶点V1，用V1作为新的起始点，重复

2、上述过程；　　⒊当到达一个其所有邻接的顶点都已被访问过的顶点Vi时，就退回到新近被访问过的顶点Vi-　1，继续访问Vi-1尚未访问的邻接点，重复上述搜索过程；　　⒋直到从任意一个已访问过的顶点出发，再也找不到未被访问过的顶点为止，遍历便告完成。　　这种搜索的次序体现了向纵深发展的趋势，所以称之为深度优先搜索。深度优先搜索算法描述：程序实现有两种方式--递归与非递归。一、递归　　递归过程为：　　ProcedureDEF-GO(step)　　　fori:=1tomaxdo　　　　if子结点符合条件then　　　　　产生新的子结点入栈；　　　　　　if子结点是目标

3、结点then输出　　　　　　　elseDEF-GO(step+1)；　　　　　　栈顶结点出栈；　　　　　endif；　　　　enddo；　　主程序为：　　ProgramDFS；　　　初始状态入栈；　　　DEF-GO(1)；　　二、非递归　　ProgramDEF(step)；　　step:=0；　　repeat　　step:=step+1；　　j:=0；p:=false　　　repeat　　　　j:=j+1；　　　　if结点符合条件then　　　　　产生子结点入栈；　　　　　　if子结点是目标结点then输出　　　　　　　elsep:=true；　　　　　el

4、se　　　　　　ifj>=maxthen回溯p:=false；　　　　endif；　　　untilp=true；15分析钻研第页训练提高信息学资料——算法JOY　　untilstep=0；　　回溯过程如下：　　ProcedureBACK；　　　step:=step-1；　　　ifstep>0then栈顶结点出栈　　　　elsep:=true；例如　八数码难题--已知８个数的起始状态如图1（ａ），要得到目标状态为图1(ｂ）。　　　　　　　２　８　３　　　　　　　　　　　　　１　２　３　　　　　　　１　６　４　　　　　　　　　　　　　８　■　４　　　　　　　７　

5、■　５　　　　　　　　　　　　７　６　５　　　　　　　　（ａ）　　　　　　　　　　　　　　　（ｂ）求解时,首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图1的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为５。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。　　　　　　　　　　　　　　　　　　图1深度优先搜索图程序：programNo8_DFS;　　　　　　{八数码的深度优先搜索

6、算法}ConstDir:array[1..4,1..2]ofinteger=((1,0),(-1,0),(0,1),(0,-1));15分析钻研第页训练提高信息学资料——算法JOYmaxN=15;　　　　　　　　　　　　　　　　｛可以承受的最大深度｝TypeT8No=array[1..3,1..3]ofinteger;tList=recordstate:T8No;x0,y0:integer;end;VarSource,Target:T8No;List,Save:array[0..maxN]oftList;　　　　　　　｛综合数据库，最优解路径｝Open,Be

7、st:integer;procedureGetInfo;　　　　　　　　　　　　　　{见程序1}FunctionSame(A,B:T8No):Boolean;　　　　　　{见程序1}functionNot_Appear(New:tList):boolean;　　　　{见程序1}procedureMove(N:tList;d:integer;varok:boolean;varNew:tList);{见程序1}procedureGetOutInfo;　　　　　　　　　　　{输出｝vari,x,y:integer;beginwriteln('total=',bes

8、t);fori:=1tobest+1dobeginf