8. 深度优先搜索(精品)

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,/31,第七讲,搜索专题,深度优先（,DFS,）,ACM,算法与程序设计,深度优先搜索算法（,Depth-First-Search,）,DFS,是由获得计算机领域的最高奖,-,图灵奖,的,霍普克洛夫特,与,陶尔扬,发明,DFS,是搜索,算法,的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点,v,的所有边都己被探寻过，搜索将回溯到发现节点,v,的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。,DFS,的时间复杂度不高（为线性时间复杂度），遍历图的效率往往非常高。因此，鉴于深度优先搜索算法的强大功能以及高效性往往被研究图论问题的专家所推崇。,时间复杂度：,O,(),；空间复杂度：,O,(,bm,),；,b-,分支系数,m-,图的最大深度,迷宫问题,首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出口出来。那老鼠会怎么走？当然可以是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意选择其中的一条继续往下走，如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去，如果遇到了出口，老鼠的旅途就算成功结束了。,深度优先搜索的基本原则：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到满足条件的目标为止。,然而要实现这样的算法，我们需要用到编程的一大利器,-,递归。,讲一个更具体的例子：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：,。好家伙，这样讲到世界末日还讲不玩，老和尚讲的故事实际上就是前面的故事情节，这样不断地调用程序本身，就形成了递归。万一这个故事中的某一个老和尚看这个故事不顺眼，就把他要讲的故事换成：“你有完没完啊！”，这样，整个故事也就嘎然而止了。,我们编程就要注意这一点，在适当的时候，就必须要有一个这样的和尚挺身而出，把整个故事给停下来，或者说他不再往深一层次搜索，要不，我们的递归就会因计算机栈空间大小的限制而溢出，称为,stack overflow,。,顺序按数字编号顺序先后访问。那么我们怎么来保证这个顺序呢？,基本思想：,从初始状态,S,开始，利用规则生成搜索树,下一层任一个,结点，检查是否出现目标状态,G,，,若未出现，以此状态,利用规则生成再下一层,任一个,结点,，再检查是否为目标节点,G,，,若未出现，继续以上操作过程，,一直进行到叶节点（即不能再生成新状态节点）,，当它仍不是目标状态,G,时，,回溯到上一层结果，取另一可能扩展搜索的分支。,生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，,，一直进行下去，直到找到目标状态,G,为止。,Boolean visitedMAX;,Status(*,VisitFunc)(int,v);,/,VisitFunc,(),为顶点的访问函数。,void,DFSTraverse(graph,G,Status,(*,Visit)(int,v),VisitFunc,=Visit;,for(v=0;v,G.vexnum;+v,)visitedv=FALSE;,for(v=0;v,G.vexnum;+v,),if(!visitedv)DFS(G,v);,void DFS(Graph G,int,v),visitedv=TRUE;,VisitFunc(G.verticesv.data,);,for(w=,FirstAdjvex(G,v);w;w,=,NextAdjvex(G,v,w,),if(!visitedw),DFS(G,w,);,递归的经典实例：阶乘,int,factorial(int,n),if(n=0)/,基线条件,(base case),return 1;,else,return n*,factorial(n,-1);/,将问题规模逐渐缩小,水仙花数,一个三位数,abc,如果满足,abc,=a3+b3+c3,那么就把这个数叫做水仙花数。,如果一个,N,位数所有数码的,N,次方的和加起来等于这个数字本身，我们把这样的数叫做广义水仙花数，容易看出来,N=3,是广义水仙花数。,现在，我们的任务是，输入一个,m(m m),/check answer,else if(deep=m),for(i=1;i=n;i+),dfs(deep,+1);,#include,#include,using namespace std;,int,m;,int,Pow(int,x,int,n),int,res=1;,while(n-)res*=x;,return res;,void,dfs(int,deep,int,curNum,int,curSum,),if(deep m)/,类似于,base case,if(,curNum,=,curSum,),printf(%dn,curNum,);,else if(deep=m),int,start=(deep=1);/,第一位不为,0,for(,int,i=start;i Max)/,深度达到极限,if(,curState,=target)/,找到目标,/.,else,for(i=1;i=,totalExpandMethod,;i+),dfs(deep,+1,expandMethod(curState,i);,大逃亡,http:/, Input,23 3 2 2.X.X.5 5 2 3.X.X.X.XX.XX.X,Sample Output,DRDRR,方法：暴力,复杂度为,O(2L),，,L,是序列长度,D,和,R,的顺序并不需要固定,当,D,和,R,的个数确定以后，我们枚举序列中,D,和,R,的个数，搜寻一条可走的矩形路线。,#include,#include,#include,#include,int,Height,Width,MinLen,MaxLen,sH,sW,;,char MAP6464;,bool,in(int,x,int,y),return x=0,bool,check(int,x,int,y),while(,in(x,y),if(,MAPxy,=X),return false;,x+=,sH,;y+=,sW,;,return true;,int,main(),int,T;,scanf(%d,while(T-),scanf(%d,%d,%d,%d,&Height,&Width,&,MinLen,&,MaxLen,);,for(,int,i=0;i Height;i+),scanf(%s,MAPi,);,bool,find=false;,for(,int,L=,MinLen,;!find&L=0;,sH,-),find=dfs(0,0,sH,sW,=L-,sH,);,return 0;,char res128;,bool,dfs(int,x,int,y,int,D,int,R),if(,check(x,y)=false),return false;,if(D=0&R=0),resx,+y=0;,printf(%sn,res);,return true;,if(D 0),resx,+y=D;,if(,dfs(x,+1,y,D-1,R),return true;,if(R 0),resx,+y=R;,if(,dfs(x,y+1,D,R-1),return true;,return false;,作业：与大逃亡很相似的题目,Tempter of the Bone,http:/, Equations,http:/, interstellar expedition team has recently discovered on planet Mars some multiplication equations,which are believed to be the proof that Mars has once been the home of some intellectual species.However these equations are incomplete where some digits are missing because of the eroding power of Mars nature.Here is one example.,One way to restore this equation is to assume the 3 missing digits are 3,5,3,respectively,obtaining 123 x 45=5535,which indicates this equation may indeed be the intellectual output of Mars ancient habitants,rather than just some random numbers.There has been hot debate over this,because people arent sure whether they can restore all the equations discovered on Mars,i.e.restore the missing digits such that the multiplication equation holds.As a programmer in NASA,you are assigned the task of checking if all the equations are restorable.,Input,The first line is an integer,T,number of equations to check.Next,T,lines each contains three non-empty strings,A,B,and,C,separated by spaces.Each string contains digits(0-9)and/or asterisks*only,where an asterisk stands for a missing digit.No string begins with the digit 0.,Output,For each test case,output,Yes(Quotes,for clarity only)on a line if one can replace the asterisks with digits such that afterwards the numbers represented by,A,B,and,C,satisfy,A,x,B,=,C,.Otherwise output No instead.Note that an asterisk must be replaced with exactly one digit(0-9)and the resulting numbers,A,B,and,C,cant start with,zeros(See,sample input/output for more clarification).,The length of string,A,and,B,are at most 3,and the length of,C,is at most 6.,The length of each string