深度优先搜索.ppt

《深度优先搜索.ppt》由会员分享，可在线阅读，更多相关《深度优先搜索.ppt（31页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第七讲搜索专题搜索专题 深度优先（深度优先（DFSDFS）ACM算法与程序设计2/31深度优先搜索算法（深度优先搜索算法（Depth-First-Search）DFS是由获得计算机领域的最高奖是由获得计算机领域的最高奖-图灵奖图灵奖的的霍普克洛夫特霍普克洛夫特与与陶尔扬陶尔扬发明发明DFS是搜索是搜索算法算法的一种。是沿着树的深度遍历树的节点，的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点尽可能深的搜索树的分支。当节点v的所有边都己被探寻的所有边都己被探寻过，搜索将回溯到发现节点过，搜索将回溯到发现节点v的那条边的起始节点。这一的那条边的起始节点。这一过程一直进行到已发现从

2、源节点可达的所有节点为止。如过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。为止。属于盲目搜索。DFS的时间复杂度不高（为线性时间复杂度），遍历图的的时间复杂度不高（为线性时间复杂度），遍历图的效率往往非常高。因此，鉴于深度优先搜索算法的强大功效率往往非常高。因此，鉴于深度优先搜索算法的强大功能以及高效性往往被研究图论问题的专家所推崇。能以及高效性往往被研究图论问题的专家所推

3、崇。时间复杂度：时间复杂度：O()；空间复杂度：；空间复杂度：O(bm)；b-分支系数分支系数m-图的最大深度图的最大深度 3/31迷宫问题迷宫问题 首先我们来想象一只老鼠，在一座不见天日的迷首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出口出来。那老宫内，老鼠在入口处进去，要从出口出来。那老鼠会怎么走？当然可以是这样的：老鼠如果遇到鼠会怎么走？当然可以是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任直路，就一直往前走，如果遇到分叉路口，就任意选择其中的一条继续往下走，如果遇到死胡同，意选择其中的一条继续往下走，如果遇到死胡同，就退回到最近的一个分叉路口

4、，选择另一条道路就退回到最近的一个分叉路口，选择另一条道路再走下去，如果遇到了出口，老鼠的旅途就算成再走下去，如果遇到了出口，老鼠的旅途就算成功结束了。功结束了。深度优先搜索的基本原则：按照某种条件往前试深度优先搜索的基本原则：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到满胡同）则退回头另选通路继续搜索，直到找到满足条件的目标为止。足条件的目标为止。4/31然而要实现这样的算法，我们需要用到编程的一大利器然而要实现这样的算法，我们需要用到编程的一大利器-递归。递归。讲一个更具体的例子：从前有座山，

5、山里有座庙，庙里有讲一个更具体的例子：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：和尚在讲故事，讲什么呢？讲：。好家伙，这样。好家伙，这样讲到世界末日还讲不玩，老和尚讲的故事实际上就是前面讲到世界末日还讲不玩，老和尚讲的故事实际上就是前面的故事情节，这样不断地调用程序本身，就形成了

6、递归。的故事情节，这样不断地调用程序本身，就形成了递归。万一这个故事中的某一个老和尚看这个故事不顺眼，就把万一这个故事中的某一个老和尚看这个故事不顺眼，就把他要讲的故事换成：他要讲的故事换成：“你有完没完啊！你有完没完啊！”，这样，整个故，这样，整个故事也就嘎然而止了。事也就嘎然而止了。我们编程就要注意这一点，在适当的时候，就必须要有一我们编程就要注意这一点，在适当的时候，就必须要有一个这样的和尚挺身而出，把整个故事给停下来，或者说他个这样的和尚挺身而出，把整个故事给停下来，或者说他不再往深一层次搜索，要不，我们的递归就会因计算机栈不再往深一层次搜索，要不，我们的递归就会因计算机栈空间大小的限

7、制而溢出，称为空间大小的限制而溢出，称为stackoverflow。5/31顺序按数字编号顺序先后访顺序按数字编号顺序先后访问。那么我们怎么来保证这问。那么我们怎么来保证这个顺序呢？个顺序呢？基本思想：基本思想：从初始状态从初始状态S S开始，利用规则生成搜索树开始，利用规则生成搜索树下一层下一层任一个任一个结点，检查是否出现目标状态结点，检查是否出现目标状态G G，若未出现，以此状若未出现，以此状态态利用规则生成再下一层利用规则生成再下一层任一个任一个结点结点，再检查是否为目标，再检查是否为目标节点节点G G，若未出现，继续以上操作过程，若未出现，继续以上操作过程，一直进行到叶节点一直进行到

8、叶节点（即不能再生成新状态节点）（即不能再生成新状态节点），当它仍不是目标状态，当它仍不是目标状态G G时，时，回溯到上一层结果，取另一可能扩展搜索的分支。回溯到上一层结果，取另一可能扩展搜索的分支。生成新生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，点，扩展可能的分支生成新状态，一直进行下去，直，一直进行下去，直到找到目标状态到找到目标状态G G为止。为止。6/31BooleanvisitedMAX;St

9、atus(*VisitFunc)(intv);/VisitFunc()为顶点的访问函数。为顶点的访问函数。voidDFSTraverse(graphG,Status(*Visit)(intv)VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);voidDFS(GraphG,intv)visitedv=TRUE;VisitFunc(G.verticesv.data);for(w=FirstAdjvex(G,v);w;w=NextAdjvex(G,v,w)if(

10、!visitedw)DFS(G,w);7/31递归的经典实例：阶乘递归的经典实例：阶乘intfactorial(intn)if(n=0)/基线条件基线条件(basecase)return1;elsereturnn*factorial(n-1);/将问题规模逐渐缩小将问题规模逐渐缩小8/31水仙花数水仙花数 一个三位数abc如果满足abc=a3+b3+c3 那么就把这个数叫做水仙花数。如果一个N位数所有数码的N次方的和加起来等于这个数字本身，我们把这样的数叫做广义水仙花数，容易看出来N=3是广义水仙花数。现在，我们的任务是，输入一个m(m m)/checkanswerelseif(deep=m)

11、for(i=1;i=n;i+)dfs(deep+1);11/31#include#includeusingnamespacestd;intm;intPow(intx,intn)intres=1;while(n-)res*=x;returnres;12/31voiddfs(intdeep,intcurNum,intcurSum)if(deepm)/类似于类似于basecaseif(curNum=curSum)printf(%dn,curNum);elseif(deep=m)intstart=(deep=1);/第一位不为第一位不为0for(inti=start;iMax)/深度达到极限深度达到极

12、限if(curState=target)/找到目标找到目标/.elsefor(i=1;i=totalExpandMethod;i+)dfs(deep+1,expandMethod(curState,i);15/31大逃亡大逃亡http:/ Description love8909遇到危险了！他被困在一个迷宫中，彷徨而无助。遇到危险了！他被困在一个迷宫中，彷徨而无助。现在需要你来帮助他走出困境。他只能记住指定长度的指令现在需要你来帮助他走出困境。他只能记住指定长度的指令(指指令的长度由令的长度由MinLen和和MaxLen限定限定)，并循环执行，而且他只会，并循环执行，而且他只会向下或向右（很奇

13、怪吧向下或向右（很奇怪吧_）。他在地图的左上角，你需要告诉）。他在地图的左上角，你需要告诉他一个运动序列，即向下（他一个运动序列，即向下（D）或向右（）或向右（R），使他能够成功走），使他能够成功走出这个图且不碰到陷阱。出这个图且不碰到陷阱。如果还不明白，可以参看图片。图如果还不明白，可以参看图片。图片片1，2对应样例的第对应样例的第1组，图片组，图片3对应样例的第对应样例的第2组。组。16/31Input第一行为第一行为1个整数个整数T，表示有，表示有T组测试数据组测试数据第二行为第二行为4个整数个整数Height,Width,MinLen,MaxLen，分别表示地，分别表示地图的高，宽，命

14、令序列的最小和最大长度。图的高，宽，命令序列的最小和最大长度。3=Height,Width=60,2=MinLen=MaxLen=35第三行至第第三行至第Height+2行为地图信息。其中行为地图信息。其中.表示空地，表示空地，X表表示陷阱。示陷阱。Output只有一行，为命令序列（只含只有一行，为命令序列（只含D,R）。）。注意：如果有多解，输入命令长度最短的；依然有多解，输出注意：如果有多解，输入命令长度最短的；依然有多解，输出字典序最小的（字典序最小的（D的字典序比的字典序比R小），数据保证一定存在一组解。小），数据保证一定存在一组解。字典序：字符串从前往后依次比较，第一个字符不同的位置

15、，字典序：字符串从前往后依次比较，第一个字符不同的位置，字符较小的字符串字典序较小，详情参见字典。字符较小的字符串字典序较小，详情参见字典。17/31SampleInput23322.X.X.5523.X.X.X.XX.XX.XSampleOutputDRDRR 18/31方法：暴力方法：暴力复杂度为复杂度为O(2L)，L是序列长度是序列长度D和和R的顺序并不需要固定的顺序并不需要固定当当D和和R的个数确定以后，我们枚举序列中的个数确定以后，我们枚举序列中D和和R的个数，搜寻一条可走的矩形路线。的个数，搜寻一条可走的矩形路线。19/31#include#include#include#incl

16、udeintHeight,Width,MinLen,MaxLen,sH,sW;charMAP6464;boolin(intx,inty)returnx=0&x=0&yWidth;boolcheck(intx,inty)while(in(x,y)if(MAPxy=X)returnfalse;x+=sH;y+=sW;returntrue;20/31intmain()intT;scanf(%d,&T);while(T-)scanf(%d%d%d%d,&Height,&Width,&MinLen,&MaxLen);for(inti=0;iHeight;i+)scanf(%s,MAPi);boolfin

17、d=false;for(intL=MinLen;!find&L=0;sH-)find=dfs(0,0,sH,sW=L-sH);return0;21/31charres128;booldfs(intx,inty,intD,intR)if(check(x,y)=false)returnfalse;if(D=0&R=0)resx+y=0;printf(%sn,res);returntrue;if(D0)resx+y=D;if(dfs(x+1,y,D-1,R)returntrue;if(R0)resx+y=R;if(dfs(x,y+1,D,R-1)returntrue;returnfalse;22/3

18、1作业：与大逃亡很相似的题目作业：与大逃亡很相似的题目TempteroftheBonehttp:/ SampleOutputYesNo 27/31枚举两个乘数再检查是否满足等式。枚举两个乘数再检查是否满足等式。递归搜索完成递归搜索完成这个题目和这个题目和GoogleCodeJamChina2006第二轮第二轮的的500分类似。分类似。Thereverse()AlgorithmAusefulSTLalgorithmisreverse().Thisalgorithmreversestheorderofelementsinaspecifiedsequence.reverse()takestwoite

19、ratorsthatmarkthesequencesbeginningandend,respectively.Hereisanexampleofreversingtheorderofachararray:28/31#include#include#include/算法头文件调用算法头文件调用reverse算法算法stringA,B,C;intlena,lenb,lenc;inta3,b3;boolflag=false;intmain()intncase;scanf(%d,&ncase);while(ncase-)scanf(%s%s%s,A,B,C);lena=A.length();lenb=

20、B.length();lenc=C.length();reverse(A.begin(),A.end();reverse(B.begin(),B.end();reverse(C.begin(),C.end();for(inti=0;i3;+i)ai=0,bi=0;flag=false;dfs(0);if(flag)printf(Yesn);elseprintf(Non);return0;29/31voiddfs(intn)if(flag)return;if(n=lena)dfs1(0);return;if(An=*)for(intj=(n=lena-1);j=9;+j)an=j;dfs(n+1);elsean=An-0;dfs(n+1);30/31voiddfs1(intn)if(flag)return;if(n=lenb)check();return;if(Bn=*)for(intj=(n=lenb-1);j=9;+j)bn=j;dfs1(n+1);elsebn=Bn-0;dfs1(n+1);31/31voidcheck()intx=a0+a1*10+a2*100;inty=b0+b1*10+b2*100;intz=x*y;for(inti=0;i=10)return;if(z=Clenc-1-0|Clenc-1=*)flag=true;