深度优先搜索

1、深度优先搜索一、搜索过程深度优先搜索的搜索过程类似树的先序遍历，也叫回溯法。搜索过程如下：从源节点开始发现有一节点 V,如果v还有未探测到的边，就沿此边继续探测下去，当 节点V的所有边都被探测过， 搜索过程将回溯到最初发现 V点的源节点。这一过程一直进行 到已发现从源节点可达的所有节点为止。这显然是一个递归过程。为了在遍历过程中区分顶点是否被访问,往往可以引入一个数组,如以mark1.n 作为标记。数组的元素取 0和 1,初值为 0。当节点被访问时,与节点相应得数组元素为1,每次访问节点时, 都得先检查它的标记值, 找 0值得节点访问, 并深度继续。 深度大的先得到 扩展,具有“后产生先扩展”

2、的特点,因此在数据结构上采用堆栈来存储（新节点入栈,节 点不能扩展时,栈定出栈） 。二、搜索特点1、由于深度搜索过程中有保留已扩展节点,则不致于重复构造不必要的子树系统。2、 深度优先搜索并不是以最快的方式搜索到解, 因为若目标节点在第 i 层的某处,必 须等到该节点左边所有子树系统搜索完毕之后, 才会访问到该节点, 因此, 搜索效率还取决 于目标节点在解答树中的位置。3、由于要存储所有已被扩展节点,所以需要的内存空间往往比较大。4、深度优先搜索所求得的是仅仅是目前第一条从起点至目标节点的树枝路径,而不是所有通向目标节点的树枝节点的路径中最短的路径。5、适用范围： 适用于求解一条从初始节点至目

3、标节点的可能路径的试题。若要存储所有解答路径,可以再建立其它空间, 用来存储每个已求得的解。若要求得最优解,必须记下达到目前目标的路径和相应的路程值, 并与前面已记录的值进行比较, 保留其中最优解, 等 全部搜索完成后,把保留的最优解输出。三、算法描述1、算法数据结构描述：深度优先搜索时，最关键的是结点扩展（OPEN ）表的生成，它是一个栈，用于存 放目前搜索到待扩展的结点, 当结点到达深度界限或结点不能再扩展时, 栈顶结点出栈, 放 入CLOSE表（存放已扩展节点），继续生成新的结点入栈 OPEN表，直到搜索到目标结点或 OPEN栈空为止。具体算法如下： 把起始结点S放到非扩展结点 OPEN

4、表中（后进先出的堆栈），如果此结点为一目标 结点,则得到一个解。 如果OPEN为一空表，则搜索失败退出。 取OPEN表最前面（栈顶）的结点，并把它放入CLOSED勺扩展结点表中，并冠以顺序 编号n。 如果结点n的深度等于最大深度，则转向2。 否则，扩展结点n,产生其全部子结点，把它们放入OPEN表的前头（入栈），并配上指向n的返回指针；如果没有后裔，则转向2。 如果后继结点中有任一个为目标结点,则求得一个解,成功退出；否则,转向2。2、算法程序描述： 递归递归过程为：Procedure DEF-GO(step) for i:=1 to max do if 子结点符合条件 then 产生新的子结

5、点入栈； 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

6、p=true ； until step=0 ； 回溯过程如下： Procedure BACK ； step:=step-1 ； if step0 then 栈顶结点出栈 else p:=true ；第 1 页 共 11 页例如八数码难题-已知8个数的起始状态如图1 (a)，要得到目标状态为图 1( b)。2831231648475765(a)(b)图1求解时，首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图2的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为5。 沿着一条路径进行下去， 态或OPEN表为空为止。粗线条路径表示求

7、得的一个解。 从图中可见，深度优先搜索过程是 直到深度界限为止， 回溯一步，再继续往下搜索，直到找到目标状图2四、关于深度优先搜索的下界对于许多问题，深度优先搜索查找的解答树可能含有无穷分支(深度优先搜索误入无穷分支就不可能找到目标节点)，或者其深度可能至少要比某个可以接受的解答系列的已知上 限还要深，或者能估计出目标节点不会超过多少层。为了避免可能太长的路径，给出一个节点扩展的最大深度，即深度界限D，任何节点达到了 D，那么都将它们作为没有后继节点处 理。如图2我们设置深度界限为5, 如果我们不对它的深度进行限定，那么第5层以下可以产生大量的搜索节点，而目标节点可以在第5层找到。深度优先搜索

8、是最常用的算法之一，而确定“深度D”是解题的关键，因为我们需要它消除不必要的搜索，提高搜索效率。估算“深度D”的方法：无章可循，凭经验和大致的计算， 在时间和空间允许的范围内， 宁大勿小。例题1:设有A, B, C, D, E五人从事J1, J2 , J3, J4 , J5五项工作，每人只能从事一项，他 们的效益如下，求最佳安排使效益最高。第3页共11页分析：每人选择五项工作中的一项，在各种选择的组合中，找到效益最高的的一种组合 输出。算法步骤：1数据库：用数组f构成堆栈存放产生的结点；数组g存放当前最高效益结点的组合； 数组p作为结点是否选择过的标志位。2结点的产生： 选择p (i)=0 的

9、结点；(2)判断效益是否高于g记录结点的效益，是高于则更新g数组及最高效益值。3搜索策略：深度优先搜索。源程序如下：program examl;con stdata: array 1.5,1.5 of in teger=(13,11,10,4,7),(13,10,10,8,5),(5,9,7,7,4), (15,12,10,11,5),(10,11,8,8,4);vari,max: in teger;f,g: array 1.5 of in teger;选择最佳效益结点的组合p: array 1.5 of in teger; procedure go(step,t: in teger); va

10、ri: in teger;beginfor i:=1 to 5 doif pi=0 the n begi n fstep:=i; pi:=1; t:=t+datastep,i;if stepmax the n beg in max:=t; g:=f;en d;t:=t-datastep,i;pi:=O;en d;en d;beginmax:=0;for i:=1 to 5 do pi:=0;go(1,0)；write In;for i:=1 to 5 do write(chr(64+i),:J,gi,”:3);write In;write In (supply: ,max);en d.例题2:

11、马的遍历中国象棋半张棋盘如图 4( a)所示。马自左下角往右上角跳。今规定只许往右跳，不 许往左跳。比如图 4 (a)中所示为一种跳行路线，并将所经路线打印出来。打印格式为：分析：如图4( b),马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：1：(i,j )i+2,j+1 )；(i3,j8)2:(i,j )i+1,j+2 )；(i4,j0,j1,j); writeln(4,8,t:5); readln;end;procedure try(i:integer); 搜索 varj:integer;beginfor j:=1 to 4 doif (ai-1,1+xj,1

12、=0) and (ai-1,1+xj,1=0) and (ai-1,2+xj,20) thenbeginflag:=flag+j;booki:=j;if i=5 then printelse try(i+1);flag:=flag-j;booki:=0;end;end;beginflag:=;c:=0;try(1);readlnend.输出结果：zhang: C wang: Aliu: B sun: D li: E六、深度优先搜索（二）前面用深度优先搜索算法求解问题的过程中，用堆栈来存放产生的结点，因此只保留了与当前结点有关的父背结点，这样可以节约大量存储空间。但如果求解的问题要求保留在搜索过

13、程中产生的全部结点，算法需要如何设计呢？可以用原综合数据库存放产生的结点， 每个结点包括结点数据和父结点指针两项。 再设 置两个索引表：OPEN表和CLOSE表，OPEN表放还未扩展完其子结点的结点编号， CLOSE 表放已扩展完的结点编号。为实现最新产生的结点先扩展的深度优先原则，OPEN表设计成堆栈形式。算法设计如下：S1 :初始化数据库，根结点放入数据库；S2: CLOSE表为空，根结点编号压入 OPEN表；S3:女口 OPEN表为空，则转 S7；S4:弹出OPEN表顶的结点为当前结点，扩展她的新子结点Mj存入数据库，并把编号压入OPEN表中；S5:如果Mj是目标结点，则输出或记录；S6

14、:返回S3；S7:结束处理。例题4:六个城市之间道路联系的示意图如下图所示。连线表示两城市间有道路相通，连线 旁的数字表示路程。请编写程序，有计算机找出从 G城到C6城的没有重复城市的所有不同 路径，按照路程总长度的大小从小到大地打印出来这些路径。输出格式：1: 1-2-5-6con st=14con st=153: 1-3-5-6con st=16第9页共11页【分析】道路之间的联系可以用一个6 X 6的“邻接距阵”（即二维数组）LINK来表示,LINK （i,j）的值表示Ci到Cj城之间的路程，如果值等于零表示没有通路。12345610480002403460383022040420495

15、0624046000940建立产生式系统：其中数据库用数组C1C6路径，LONG记录路径长度;产生式规则：R为下一个城市编号,OPEN做索引表，用 NODE （字符传数组）记录20且Cr没有到过 THEN增加一个NODE元素，把新增元素赋值为：K+R。增加一个OPEN元素，记下NODE元素的位置。最后一行可以省 统计长度 搜索策略：见源程序program exam4;constmax=maxint;link:array1.5,1.6 of integer=(0,4,8,0,0,0),(4,0,3,4,6,0),(8,3,0,2,2,0),(0,4,2,0,4,9),(0,6,2,4,0,4);

16、 邻接表：略，因为到达 C6 后不能再到别的城市 typepath=string6; 字符串记录路径 varopen:array1.6 of integer; 索引表 node:array1.100 of path; 记录所有路径 count,i,n:integer;procedure try(k,dep:integer); 搜索过程 varr,len:byte;temp:path;begintemp:=nodeopendep; 取出 NODE 表中最后一个元素 len:=length(temp);if pos(6,temp)0 then exit 不能再到别的城市 elsefor r:=2

17、to 6 doif(linkk,r0) and (pos(chr(48+r),temp)=0) thenbegininc(n);noden:=temp+chr(48+r); opendep+1:=n;try(r,dep+1) 搜索下一个城市 endend;procedure print; 打印 varf,i,j,k,l:integer;bool:array1.100 of boolean; 记录某路径是否已经打印 long:array1.100 of integer; 记录某路径的总长度 begincount:=0;for i:=1 to n doif nodei,length(nodei)6 thenbooli:=falseelsebegin booli:=true; inc(count);longi:=0;for j:=2