2022年深度优先搜索 .pdf

《2022年深度优先搜索 .pdf》由会员分享，可在线阅读，更多相关《2022年深度优先搜索 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、后进先出的堆栈) ，如果此结点为一目标结点，则得到一个解。 如果 OPEN 为一空表，则搜索失败退出。 取 OPEN 表最前面 ( 栈顶 ) 的结点， 并把它放入CLOSED 的扩展结点表中，并冠以顺序编号。 如果结点的深度等于最大深度，则转向。 否则，扩展结点，产生其全部子结点，把它们放入OPEN 表的前头 ( 入栈 ) ，并配上指向的返回指针；如果没有后裔，则转向。 如果后继结点中有任一个为目标结点，则求得一个解，成功退出；否则，转向。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 11 页名师精编精品教案2、算法程序描述： 递归递

5、归过程为：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

6、；else if j=max then 回溯 p:=false；endif ；until p=true；until step=0；回溯过程如下：Procedure BACK ；step:=step-1；if step0 then 栈顶结点出栈else p:=true；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 11 页名师精编精品教案例如八数码难题 - 已知个数的起始状态如图1（） ，要得到目标状态为图1( ） 。（）（）图 1求解时 , 首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图2 的搜索树。 图中，所有结点

7、都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为。粗线条路径表示求得的一个解。从图中可见， 深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步， 再继续往下搜索，直到找到目标状态或 OPEN 表为空为止。图 2四、关于深度优先搜索的下界对于许多问题， 深度优先搜索查找的解答树可能含有无穷分支（深度优先搜索误入无穷分支就不可能找到目标节点），或者其深度可能至少要比某个可以接受的解答系列的已知上限还要深， 或者能估计出目标节点不会超过多少层。为了避免可能太长的路径，给出一个节点扩展的最大深度，即深度界限D，任何节点达到了D，那么都将它们作为没有后继节点

8、处理。如图 2 我们设置深度界限为，如果我们不对它的深度进行限定，那么第 5 层以下可以产生大量的搜索节点，而目标节点可以在第5 层找到。深度优先搜索是最常用的算法之一，而确定“深度D”是解题的关键，因为我们需要它消除不必要的搜索，提高搜索效率。估算“深度 D”的方法： 无章可循， 凭经验和大致的计算，在时间和空间允许的范围内，宁大勿小。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 11 页名师精编精品教案例题 1：设有 A，B，C，D，E五人从事J1，J2，J3，J4，J5 五项工作，每人只能从事一项，他们的效益如下，求最佳安排使效

9、益最高。图3分析 : 每人选择五项工作中的一项，在各种选择的组合中，找到效益最高的的一种组合输出。算法步骤 : 数据库：用数组构成堆栈存放产生的结点；数组存放当前最高效益结点的组合；数组作为结点是否选择过的标志位。结点的产生：(1) 选择 (i)=0的结点；(2) 判断效益是否高于记录结点的效益，是高于则更新数组及最高效益值。搜索策略 : 深度优先搜索。源程序如下 : program exam1; const data: array 1.5,1.5 of integer =(13,11,10,4,7),(13,10,10,8,5),(5,9,7,7,4), (15,12,10,11,5),(1

10、0,11,8,8,4); var i,max: integer; f,g: array 1.5 of integer; p: array 1.5 of integer; procedure go(step,t: integer); 选择最佳效益结点的组合var i: integer; begin for i:=1 to 5 do if pi=0 then begin fstep:=i; pi:=1; t:=t+datastep,i; if stepmax then begin max:=t; g:=f; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -

11、第 4 页，共 11 页名师精编精品教案end; t:=t-datastep,i; pi:=0; end; end; begin max:=0; for i:=1 to 5 do pi:=0; go(1,0); writeln; for i:=1 to 5 do write(chr(64+i),:J,gi,:3); writeln; writeln(supply: ,max); end.例题 2：马的遍历中国象棋半张棋盘如图4（a）所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如图4（a）中所示为一种跳行路线，并将所经路线打印出来。打印格式为：0，0-2,1-3,3-1,4-3,

12、5-2,7-4,8 0 1 2 3 4 5 6 7 8 （a）（ b）图 4 分析：如图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); 搜索 var j:integer; begin for j:=1 to 4 do if (ai-1,1+xj,1=0) and (ai-1,1+xj,1=0) and (ai-

13、1,2+xj,20) then begin flag:=flag+j;booki:=j; if i=5 then print else try(i+1); flag:=flag-j;booki:=0; end; end; begin flag:=;c:=0;try(1); readln end. 输出结果：zhang: C wang: A 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 11 页名师精编精品教案liu: B sun: D li: E 六、深度优先搜索（二）前面用深度优先搜索算法求解问题的过程中，用堆栈来存放产生的结点，因

14、此只保留了与当前结点有关的父背结点，这样可以节约大量存储空间。但如果求解的问题要求保留在搜索过程中产生的全部结点，算法需要如何设计呢？可以用原综合数据库存放产生的结点，每个结点包括结点数据和父结点指针两项。再设置两个索引表： OPEN 表和 CLOSE 表，OPEN 表放还未扩展完其子结点的结点编号，CLOSE表放已扩展完的结点编号。为实现最新产生的结点先扩展的深度优先原则，OPEN 表设计成堆栈形式。算法设计如下：S1：初始化数据库，根结点放入数据库；S2：CLOSE 表为空，根结点编号压入OPEN 表；S3：如 OPEN 表为空，则转S7；S4：弹出 OPEN 表顶的结点为当前结点，扩展她

15、的新子结点Mj存入数据库，并把编号压入 OPEN 表中；S5：如果 Mj是目标结点，则输出或记录；S6：返回 S3；S7：结束处理。例题 4：六个城市之间道路联系的示意图如下图所示。连线表示两城市间有道路相通，连线旁的数字表示路程。请编写程序， 有计算机找出从C1城到 C6城的没有重复城市的所有不同路径，按照路程总长度的大小从小到大地打印出来这些路径。输出格式：1: 1-2-5-6 const=14 2: 1-2-3-5-6 const=15 3: 1-3-5-6 const=16 .【分析】 道路之间的联系可以用一个66 的“邻接距阵”（即二维数组） LINK 来表示，LINK (i,j)

16、的值表示Ci到 Cj城之间的路程，如果值等于零表示没有通路。1 2 3 4 5 6 1 0 4 8 0 0 0 2 4 0 3 4 6 0 3 8 3 0 2 2 0 4 0 4 2 0 4 9 5 0 6 2 4 0 4 6 0 0 0 9 4 0 建立产生式系统：其中数据库用数组OPEN 做索引表，用NODE（字符传数组）记录路径， LONG 记录路径长度；产生式规则：R 为下一个城市编号，2R6，K 是当前路径，则有5 条规则：IF LINK （KLENGTH （K），R）0 且 CR没有到过THEN 增加一个 NODE 元素，把新增元素赋值为：K+R 。增加一个 OPEN 元素，记下N

17、ODE 元素的位置。C1C2C3 C5 C4C64 4 4 9 4 2 8 3 6 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 11 页名师精编精品教案搜索策略：见源程序program exam4; const max=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); 邻接表： 最后一行可以省略，因为到达C6后不能再到别的城市type path=string6;

18、字符串记录路径 var open:array1.6 of integer; 索引表 node:array1.100 of path; 记录所有路径 count,i,n:integer; procedure try(k,dep:integer); 搜索过程 var r,len:byte; temp:path; begin temp:=nodeopendep; 取出 NODE 表中最后一个元素 len:=length(temp); if pos(6,temp)0 then exit 不能再到别的城市else for r:=2 to 6 do if(linkk,r0) and (pos(chr(48

19、+r),temp)=0) then begin inc(n);noden:=temp+chr(48+r); opendep+1:=n;try(r,dep+1) 搜索下一个城市end end; procedure print; 打印 var f,i,j,k,l:integer; bool:array1.100 of boolean; 记录某路径是否已经打印long:array1.100 of integer; 记录某路径的总长度begin count:=0; for i:=1 to n do if nodei,length(nodei)6 then booli:=false else begin

20、 booli:=true; inc(count);longi:=0; for j:=2 to length(nodei) do longi:=longi+linkord(nodei,j-1)-48,ord(nodei,j)-48; 统计长度 end; for i:=1 to count do begin 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 11 页名师精编精品教案k:=maxint; for j:=1 to n do if (boolj) and (longj,nodel,j); 输出路径 writeln(cost=,k) 输出总长度 end;输出 readln end; begin n:=1;node1:=1;open1:=1; 赋初始值 try(1,1); 搜索 print; 打印 end. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 11 页