深度优先搜索法

深度优先搜索法深度优先搜索法以树的搜索为例，深度优先搜索法是优先扩展尚未扩展的且具有最大深度的节点，广度优先搜索法是在扩展完第K层的节点以后才扩展K+1层的节点。深度优先搜索法与前面讲的回溯法差不多。其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树，搜索树起记录路径和状态判断的作用。为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。在回溯法中，我们已分析了非递归的实现过程，在这里就只讨论深度优先的递归实现方法。深度优先搜索的...

深度优先搜索法以树的搜索为例，深度优先搜索法是优先扩展尚未扩展的且具有最大深度的节点，广度优先搜索法是在扩展完第K层的节点以后才扩展K+1层的节点。深度优先搜索法与前面讲的回溯法差不多。其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树，搜索树起记录路径和状态判断的作用。为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。在回溯法中，我们已分析了非递归的实现过程，在这里就只讨论深度优先的递归实现方法。深度优先搜索的递归实现过程：proceduredfs(i);fori:=1tordoif子节点mr符合条件then产生的子节点mr入栈；if子节点mr是目标节点then输出elsedfs(i+1);栈顶元素出栈（即删去mr）；endif；endfor；在讲解递推法时，我们讨论了用递推法解骑士游历问题，在这里我们看看如何用深度优先搜索法求解此题。例1：骑士游历问题；设有一个n*m的棋盘，在棋盘上任一点有一个中国象棋马，马走的规则为：1.马走日字2.马只能向右走。当n，m输入之后，找出一条从左下到右上角的路径。例如：输入n=4，m=4，输出：路径的格式：（1，1）—>(2,3)->(4,4)，若不存在路径，则输出“NO”。算法分析：我们以4*4的棋盘为例进行分析，用树形结构表示马走的所有过程，求从起点到终点的路径，实际上就是从根节点开始深度优先搜索这棵树。马从（1，1）开始，按深度优先搜索法，走一步到达（2，3），判断是否到达终点，若没有，则继续向前走，在走一步到达（4，4），然后判断是否到达终点，若到达则退出，搜索过程结束。为了减少搜索次数，在马走的过程中，判断下一步所走的位置是否在棋盘上，如果不在棋盘上，则选择另一条路径再走。程序如下：constdx:array[1..4]ofinteger=(2,2,1,1);dy:array[1..4]ofinteger=(1,-1,2,-2);typemap=recordx,y:integer;end;varI,n,m:integer;a:array[0..50]ofmap;proceduredfs(i:integer);varj:integer;beginforj:=1to4doif(a[i-1].x+dx[j]>0)and(a[i-1].x+dx[j]<=n)and(a[i-1].y+dy[j]>0)and(a[i-1].y+dy[j]<=m)then{判断是否在棋盘上}begina[i].x:=a[i-1].x+dx[j];a[i].y:=a[i-1].y+dy[j];{入栈}if(a[i].x=n)and(a[i].y=m)thenbeginwrite(‘(‘,1,’,’,1,’)’);forj:=2toIdowrite(‘->(’,a[j].x,’,’,a[j].y,’)’);halt;{输出结果并退出程序}end;dfs(i+1);{搜索下一步}a[i].x:=0;a[i].j:=0;{出栈}end;end;begina[1].x:=1;a[1].y:=1;readln(n,m);dfs(2);writeln(‘no’);end.从上面的例子我们可以看出，深度优先搜索算法有两个特点：１.已产生的节点按深度排序，深度大的节点先得到扩展，即先产生它的子节点。２.深度大的节点是后产生的，但先得到扩展，即“后产生先扩展”，与栈的工作原理相同，因此用堆栈作为该算法的主要数据结构，存储产生的节点。对于不同的问题，深度优先搜索算法基本上是一样的，但在具体处理方法和编程技巧上有都不相同，甚至有很大的差别。我们再看看另一个例子。例题2：选数（NOIP2002pj）问题描述：已知n个整数x1，x2，…xn，以及一个整数k（k0)doinc(i);Ifsqr(i)>stheninc(ans){若为素数则总数加1}end;Proceduredfs(I,m:byte);{搜索第i个数}Varj:byte;{j表示第i个数的位置}Beginforj:=mton-k+Ido{枚举第i个数}Begininc(s,a[j]);{入栈}Ifi=kthenprime(s)Elsedfs(i+1,j+1);{继续搜索第i+1个数}Dec(s,a[j]){出栈}EndEnd;BeginReadln(n,k);Fori:=1tondoread(a[j]);Ans:=0;s:=0;Dfs(1,1);Writeln(ans);End.从上面的两个例子我们可以看出，用递归实现深度优化搜索比非递归更加方便。在使用深度搜索法解题时，搜索的效率并不高，所以要重视对算法的优化，尽可能地减少搜索范围，提高程序的速度。

                    本文档为【深度优先搜索法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

深度优先搜索法

你可能还喜欢