2022年深度优先搜索.docx

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

1、精选学习资料 - - - - - - - - - 名师精编 精品教案深度优先搜寻（补充教案）一、搜寻过程深度优先搜寻的搜寻过程类似树的先序遍历,也叫回溯法；搜寻过程如下：从源节点开头发觉有一节点v,假如 v 仍有未探测到的边,就沿此边连续探测下去,当节点 v 的全部边都被探测过,搜寻过程将回溯到最初发觉v 点的源节点； 这一过程始终进行到已发觉从源节点可达的全部节点为止；这明显是一个递归过程；为了在遍历过程中区分顶点是否被拜访,往往可以引入一个数组,如以 mark1.n 作为标记；数组的元素取 0 和 1,初值为 0；当节点被拜访时,与节点相应得数组元素为 1,每次拜访节点时, 都得先检查它的

2、标记值,找 0 值得节点拜访, 并深度连续； 深度大的先得到扩展,具有“ 后产生先扩展” 的特点,因此在数据结构上采纳堆栈来储备（新节点入栈,节点不能扩展时,栈定出栈）；二、搜寻特点1、 由于深度搜寻过程中有保留已扩展节点,就不致于重复构造不必要的子树系统；2、 深度优先搜寻并不是以最快的方式搜寻到解,由于如目标节点在第 i 层的某处,必须等到该节点左边全部子树系统搜寻完毕之后,才会拜访到该节点,因此, 搜寻效率仍取决于目标节点在解答树中的位置；3、 由于要储备全部已被扩展节点,所以需要的内存空间往往比较大；4、 深度优先搜寻所求得的是仅仅是目前第一条从起点至目标节点的树枝路径,而不是全部通向

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

4、直到搜寻到目标结点或 把起始结点S 放到非扩展结点OPEN表中 后进先出的堆栈 ,假如此结点为一目标结点,就得到一个解； 假如 OPEN为一空表,就搜寻失败退出； 取 OPEN表最前面 栈顶 的结点, 并把它放入 编号； 假如结点的深度等于最大深度,就转向；CLOSED的扩展结点表中, 并冠以次序 否就,扩展结点,产生其全部子结点,把它们放入 OPEN表的前头 入栈 ,并配上指向的返回指针；假如没有后裔,就转向； 假如后继结点中有任一个为目标结点,就求得一个解,胜利退出；否就,转向；名师归纳总结 - - - - - - -第 1 页,共 11 页精选学习资料 - - - - - - - - -

5、 名师精编 精品教案2、算法程序描述： 递归 递归过程为：Procedure DEF-GOstep for i:=1 to max do if 子结点符合条件 then 产生新的子结点入栈；if 子结点是目标结点 then 输出else DEF-GOstep+1；栈顶结点出栈；endif ；enddo；主程序为：Program DFS ；初始状态入栈；DEF-GO1； 非递归 Program DEFstep；step:=0 ；repeat step:=step+1；j:=0 ；p:=false repeat j:=j+1；if 结点符合条件 then 产生子结点入栈；if 子结点是目标结点 t

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

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

8、D,那么都将它们作为没有后继节点处理；如图 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,1

10、2,10,11,5,10,11,8,8,4; var i,max: integer; f,g: array 1.5 of integer; p: array 1.5 of integer; procedure gostep,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; 名师归纳总结 - - - - - - -第 4 页,共 11 页精选学习资

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

12、,4-3,5-2,7-4,8 4 1 3 2 马1 0 1 2 3 4 5 6 7 8 4 （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; writeln4,8,t:5; readln; end; procedure tryi: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

13、ai-1,2+xj,20 then begin flag:=flag+j;booki:=j; if i=5 then print else tryi+1; flag:=flag-j;booki:=0; end; end; begin flag:=;c:=0;try1; 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、她的新子结点 压入 OPEN 表中；S5：假如 M j是目标结点,就输出或记录；S6：返回 S3；S7：终止处理；M j存入数据库,并把编号例题 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 .【分析】 道路之间的联系可以用一个6 6 的“ 邻接距阵” （即二维数组） LINK 来表示,LI

16、NK i,j 的值表示 Ci到 Cj城之间的路程,假如值等于零表示没有通路；1 2 3 4 5 6 C1C24 C49 1 0 4 8 0 0 0 4 3 6 2 4 0 3 4 6 0 4 C63 8 3 0 2 2 0 8 2 4 4 0 4 2 0 4 9 C3 2 5 0 6 2 4 0 4 C5 6 0 0 0 9 4 0 OPEN 做索引表,用NODE （字符传数组）记录建立产生式系统：其中数据库用数组路径, LONG 记录路径长度；名师归纳总结 产生式规章： R 为下一个城市编号,2R6,K 是当前路径,就有5 条规章：第 9 页,共 11 页IF LINK （KLENGTH （

17、K）,R）0 且 CR没有到过THEN 增加一个 NODE 元素,把新增元素赋值为：K+R ；增加一个 OPEN 元素,登记NODE 元素的位置；- - - - - - -精选学习资料 - - - - - - - - - 名师精编 精品教案搜寻策略：见源程序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 tryk,dep:integer; 搜寻过程 var r,len:byte; temp:path; begin temp:=nodeopendep; 取出 NODE 表中最终一个元素 len:=lengthtemp; if pos6,temp0 then exit 不能再到别的城市else for r:=2 to 6 do iflinkk,r0 and poschr48+r,temp=0

19、 then begin incn;noden:=temp+chr48+r; opendep+1:=n;tryr,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,lengthnodei6 then booli:=false else begin booli:=true; inccou

20、nt;longi:=0; for j:=2 to lengthnodei do longi:=longi+linkordnodei,j-1-48,ordnodei,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; 输出路径 writelncost=,k 输出总长度 end; 输出 readln end; begin n:=1;node1:=1;open1:=1; 赋初始值 try1,1; 搜寻 print; 打印 end. 名师归纳总结 - - - - - - -第 11 页,共 11 页