深度优先搜索ppt课件.ppt

《深度优先搜索ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七讲搜索专题深度优先（DFS）ACM算法与程序设计深度优先搜索算法（Depth-First-Search）DFS是由获得计算机领域的最高奖-图灵奖的霍普克洛夫特与陶尔扬发明DFS是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。DFS的时间复杂度不高（为线性时间复杂

2、度），遍历图的效率往往非常高。因此，鉴于深度优先搜索算法的强大功能以及高效性往往被研究图论问题的专家所推崇。时间复杂度：O()；空间复杂度：O(bm)；b-分支系数m-图的最大深度迷宫问题首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出口出来。那老鼠会怎么走？当然可以是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意选择其中的一条继续往下走，如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去，如果遇到了出口，老鼠的旅途就算成功结束了。深度优先搜索的基本原则：按照某种条件往

3、前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到满足条件的目标为止。然而要实现这样的算法，我们需要用到编程的一大利器---递归。讲一个更具体的例子：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：…………。好家伙，这样讲到世界末日还讲不玩，老和尚讲的故事实际上就是前面的故事情节，这样不断地调用程序本身，就形成了递归。万一这个故事中的

4、某一个老和尚看这个故事不顺眼，就把他要讲的故事换成：“你有完没完啊！”，这样，整个故事也就嘎然而止了。我们编程就要注意这一点，在适当的时候，就必须要有一个这样的和尚挺身而出，把整个故事给停下来，或者说他不再往深一层次搜索，要不，我们的递归就会因计算机栈空间大小的限制而溢出，称为stackoverflow。顺序按数字编号顺序先后访问。那么我们怎么来保证这个顺序呢？基本思想：从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现

5、，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，…，一直进行下去，直到找到目标状态G为止。Booleanvisited[MAX];Status(*VisitFunc)(intv);//VisitFunc()为顶点的访问函数。voidDFSTraverse(graphG,Status(*Visit)(intv)){

6、VisitFunc=Visit;for(v=0;v

7、n){if(n==0)//基线条件(basecase){return1;}else{returnn*factorial(n-1);//将问题规模逐渐缩小}}水仙花数一个三位数abc如果满足abc=a^3+b^3+c^3那么就把这个数叫做水仙花数。如果一个N位数所有数码的N次方的和加起来等于这个数字本身，我们把这样的数叫做广义水仙花数，容易看出来N=3是广义水仙花数。现在，我们的任务是，输入一个m(m<7)，让你求出所有满足N=m的广义水仙花数。3(153370371407)5(547489272793084)方法：数据规模很小，

8、可以直接枚举所有情况，然后判断是否满足条件。难点：循环层数不确定怎么实现这个m重循环？答案：递归。m重循环的实现：voiddfs(intdeep){if(deep>m){//checkanswer}elseif(deep<=m){for(i=1;i<=n;i++