2022年深度优先搜索.docx

精选学习资料 - - - - - - - - - 名师精编 精品教案深度优先搜寻（补充教案）一、搜寻过程深度优先搜寻的搜寻过程类似树的先序遍历,也叫回溯法；搜寻过程如下：从源节点开头发觉有一节点v,假如 v 仍有未探测到的边,就沿此边连续探测下去,当节点 v 的全部边都被探测过,搜寻过程将回溯到最初发觉v 点的源节点； 这一过程始终进行到已发觉从源节点可达的全部节点为止；这明显是一个递归过程；为了在遍历过程中区分顶点是否被拜访,往往可以引入一个数组,如以 mark1.n 作为标记；数组的元素取 0 和 1,初值为 0；当节点被拜访时,与节点相应得数组元素为 1,每次拜访节点时, 都得先检查它的标记值,找 0 值得节点拜访, 并深度连续； 深度大的先得到扩展,具有“ 后产生先扩展” 的特点,因此在数据结构上采纳堆栈来储备（新节点入栈,节点不能扩展时,栈定出栈）；二、搜寻特点1、 由于深度搜寻过程中有保留已扩展节点,就不致于重复构造不必要的子树系统；2、 深度优先搜寻并不是以最快的方式搜寻到解,由于如目标节点在第 i 层的某处,必须等到该节点左边全部子树系统搜寻完毕之后,才会拜访到该节点,因此, 搜寻效率仍取决于目标节点在解答树中的位置；3、 由于要储备全部已被扩展节点,所以需要的内存空间往往比较大；4、 深度优先搜寻所求得的是仅仅是目前第一条从起点至目标节点的树枝路径,而不是全部通向目标节点的树枝节点的路径中最短的路径；5、 适用范畴： 适用于求解一条从初始节点至目标节点的可能路径的试题；如要储备所有解答路径,可以再建立其它空间,用来储备每个已求得的解；如要求得最优解,必需登记达到目前目标的路径和相应的路程值,并与前面已记录的值进行比较,保留其中最优解,等全部搜寻完成后,把保留的最优解输出；三、算法描述1、算法数据结构描述：深度优先搜寻时,最关键的是结点扩展（）表的生成,它是一个栈,用于存放目前搜寻到待扩展的结点,当结点到达深度界限或结点不能再扩展时,栈顶结点出栈, 放入 CLOSE表（存放已扩展节点） ,连续生成新的结点入栈 OPEN栈空为止；详细算法如下：OPEN表,直到搜寻到目标结点或 把起始结点S 放到非扩展结点OPEN表中 后进先出的堆栈 ,假如此结点为一目标结点,就得到一个解； 假如 OPEN为一空表,就搜寻失败退出； 取 OPEN表最前面 栈顶 的结点, 并把它放入 编号； 假如结点的深度等于最大深度,就转向；CLOSED的扩展结点表中, 并冠以次序 否就,扩展结点,产生其全部子结点,把它们放入 OPEN表的前头 入栈 ,并配上指向的返回指针；假如没有后裔,就转向； 假如后继结点中有任一个为目标结点,就求得一个解,胜利退出；否就,转向；名师归纳总结 - - - - - - -第 1 页,共 11 页精选学习资料 - - - - - - - - - 名师精编 精品教案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 子结点是目标结点 then 输出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 step>0 then else p:=true；- - - - - - -精选学习资料 - - - - - - - - - 例如名师精编精品教案1 ）；八数码难题 - 已知个数的起始状态如图1（）,要得到目标状态为图（）（）图 1求解时 , 第一要生成一棵结点的搜寻树,依据深度优先搜寻算法,我们可以生成图 2 的搜寻树； 图中,全部结点都用相应的数据库来标记,并依据结点扩展的次序加以编号；其中,我们设置深度界限为；粗线条路径表示求得的一个解；从图中可见, 深度优先搜寻过程是沿着一条路径进行下去,直到深度界限为止,回溯一步, 再连续往下搜寻,直到找到目标状态或 OPEN表为空为止；图 2四、关于深度优先搜寻的下界对于很多问题, 深度优先搜寻查找的解答树可能含有无穷分支（深度优先搜寻误入无穷分支就不行能找到目标节点）,或者其深度可能至少要比某个可以接受的解答系列的已知上限仍要深, 或者能估量出目标节点不会超过多少层；为了防止可能太长的路径,给出一个节点扩展的最大深度,即深度界限 D,任何节点达到了 D,那么都将它们作为没有后继节点处理；如图 2 我们设置深度界限为,假如我们不对它的深度进行限定,那么第 5 层以下可以产生大量的搜寻节点,而目标节点可以在第5 层找到；深度优先搜寻是最常用的算法之一,而确定“ 深度 D” 是解题的关键,由于我们需要它排除不必要的搜寻,提高搜寻效率；估算“ 深度 D” 的方法： 无章可循, 凭体会和大致的运算,宁大勿小；在时间和空间答应的范畴内,名师归纳总结 - - - - - - -第 3 页,共 11 页精选学习资料 - - - - - - - - - 名师精编 精品教案例题 1：设有 A,B,C,D,E 五人从事 J1,J2,J3,J4,J5 五项工作,每人只能从事一项,他们的效益如下,求正确支配使效益最高；图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,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 step<5 then gostep+1,t else if t>max then begin max:=t; g:=f; 名师归纳总结 - - - - - - -第 4 页,共 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; writeln'supply: ',max; end.例题 2：马的遍历中国象棋半张棋盘如图4（a）所示；马自左下角往右上角跳；今规定只许往右跳,不许往左跳；比如图4（a）中所示为一种跳行路线,并将所经路线打印出来；打印格式为：2 3 0,0->2,1->3,3->1,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）； i<3,j<8 2: （ i,j）（ i+1,j+2）； i<4,j<7 3: （ i,j）（ i-1,j+2）； i>0,j<7 4: （ i,j）（ i-2,j+1）； i>1,j<8 搜寻策略：S1: :=0,0; S2: 从 1 动身,按移动规章依次选定某个方向,假如达到的是（4,8 ）就转向S3, 否就连续搜寻下一个到达的顶点；S3: 打印路径；名师归纳总结 - - - - - - -第 5 页,共 11 页精选学习资料 - - - - - - - - - 名师精编 精品教案源程序范例：program exam2; const x:array1.4,1.2 of integer=2,1,1,2,-1,2,-2,1; 四种移动规章 var t:integer; 路径总数 a:array1.9,1.2 of integer; 路径 procedure printii:integer; 打印 var i:integer; begin inct; for i:=1 to ii-1 do writeai,1,',',ai,2,'->' writeln'4,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<=4 and ai-1,2+xj,2>=0 and ai-1,2+xj,2<=8 then begin ai,1:=ai-1,1+xj,1; ai,2:=ai-1,2+xj,2; if ai,1=4 and ai,2=8 then printi else tryi+1; 搜寻下一步 ai,1:=0;ai,2:=0 end; end; begin 主程序 try2; end.名师归纳总结 - - - - - - -第 6 页,共 11 页精选学习资料 - - - - - - - - - 名师精编 精品教案例题 3： 选书学校放寒假时,信息学竞赛辅导老师有A,B,C,D,E 五本书,要分给参与培训的张、王、刘、孙、李五位同学,每人只能选一本书；老师事先让每个人将自己宠爱的书填写在如下的表格中； 然后依据他们填写的表来安排书本,的安排方案,使每个同学都中意；期望设计一个程序帮忙老师求出全部可能同学书本A B C D E 张同学Y Y Y Y Y 王同学刘同学Y Y Y 孙同学Y Y 李同学分析：可用穷举法,先不考虑“ 每人都中意”这一条件,这样只剩“ 每人选一本且只能选一 本” 这一条件；在这个条件下,可行解就是五本书的全部全排列,一共有 5！=120 种；然 后在 120 种可行解中一一删去不符合“ 每人都中意” 的解,留下的就是此题的解答；为了编程便利,设 1,2,3, 4,5 分别表示这五本书；这五个数的一种全排列就是五 本书的一种分发； 例如 54321 就表示第 5 本书（即 E）分给张,第 4 本书（即 D）分给王, ,第 1 本书（即 A）分给李；“ 宠爱书表”可以用二维数组来表示,1 表示宠爱, 0 表示不宠爱；算法设计：S1：产生 5 个数字的一个全排列；S2：检查是否符合“ 宠爱书表” 的条件,假如符合就打印出来；S3：检查是否全部的排列都产生了,假如没有产生完,就返回 S1；S4：终止；上述算法有可以改进的地方；比如产生了一个全排列12345,从表中可以看出,选第一本书即给张同学的书,1 是不行能的,由于张只宠爱第3、4 本书；这就是说,1× × × × 一类的分法都不符合条件；由此想到,假如选定第一本书后,就立刻检查一下是否符合条件,发觉 1 是不符合的, 后面的四个数字就不必选了,这样就削减了运算量；换句话说,第一个数字只在 3、4 中挑选,这样就可以削减 3/5 的运算量；同理,选定了第一个数字后,也不应当把其他 4 个数字一次选定, 而是挑选了其次个数字后,就立刻检查是否符合条件；例如,第一个数选 3,其次个数选 4 后,立刻检查,发觉不符合条件,就应另选其次个数；这样就把 34× × × 一类的分法在产生前就删去了；又削减了一部分运算量；综上所述,改进后的算法应当是：在产生排列时,每增加一个数,就检查该数是否符合条件,不符合,就马上换一个,符合条件后,再产生下一个数；由于从第I 本书到第I+1本书的查找过程是相同的,所以可以用递归方法；算法设计如下：procedure tryi; begin for j:=1 to 5 do begin if 第 i 个同学分给第j 本书符合条件then begin 记录第 i 个数 3 if i =5 then 打印一个解名师归纳总结 - - - - - - -第 7 页,共 11 页精选学习资料 - - - - - - - - - 名师精编 精品教案else tryi+1; 删去第 i 个数字end; end; end; 源程序：program exam3; type five=1.5; const like:arrayfive,five of 0.1=0,0,1,1,0,1,1,0,0,1, 0,1,1,0,0,0,0,0,1,0,0,1,0,0,1; name:arrayfive of string6='zhang','wang','liu','sun','li' var book:array1.5 of 0.5; flag:set of five; c:integer; procedure print; var i:integer; begin incc;writeln'answer',c,':' for i:=1 to 5 do writelnnamei:10,':',chr64+booki; end; procedure tryi:integer; var j:integer; begin for j:=1 to 5 do if notj in flag and likei,j>0 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 六、深度优先搜寻（二）前面用深度优先搜寻算法求解问题的过程中,用堆栈来存放产生的结点,因此只保留了与当前结点有关的父背结点,这样可以节省大量储备空间；但假如求解的问题要求保留在搜索过程中产生的全部结点,算法需要如何设计呢？可以用原综合数据库存放产生的结点,每个结点包括结点数据和父结点指针两项；再设置两个索引表： OPEN 表和 CLOSE 表,OPEN 表放仍未扩展完其子结点的结点编号,CLOSE表放已扩展完的结点编号；为实现最新产生的结点先扩展的深度优先原就,OPEN 表设计成堆栈形式；算法设计如下：S1：初始化数据库,根结点放入数据库；S2：CLOSE 表为空,根结点编号压入 OPEN 表；S3：如 OPEN 表为空,就转 S7；S4：弹出 OPEN 表顶的结点为当前结点,扩展她的新子结点 压入 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 来表示,LINK 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 （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; 字符串记录路径 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 pos'6',temp>0 then exit 不能再到别的城市else for r:=2 to 6 do iflinkk,r>0 and poschr48+r,temp=0 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,lengthnodei<>'6' then booli:=false else begin booli:=true; inccount;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<kthen begin k:=longj;l:=j end; booll:=false; writei:2,':1' for j:=2 to lengthnodel do write'->',nodel,j; 输出路径 writeln'cost=',k 输出总长度 end; 输出 readln end; begin n:=1;node1:='1'open1:=1; 赋初始值 try1,1; 搜寻 print; 打印 end. 名师归纳总结 - - - - - - -第 11 页,共 11 页