9.-深度优先搜索

第八讲搜索专题深度优先（DFS）ACM算法与程序设计数学科学学院：汪小平[e-mail]2/34深度优先搜索算法（Depth-First-Search）•DFS是由获得计算机领域的最高奖-图灵奖的霍普克洛夫特与陶尔扬发明•DFS是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。•DFS的时间复杂度不高（为线性时间复杂度），遍历图的效率往往非常高。因此，鉴于深度优先搜索算法的强大功能以及高效性往往被研究图论问题的专家所推崇。•时间复杂度：O(bm)；空间复杂度：O(bm)；b-分支系数m-图的最大深度3/34迷宫问题•首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出口出来。那老鼠会怎么走？当然可以是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意选择其中的一条继续往下走，如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去，如果遇到了出口，老鼠的旅途就算成功结束了。•深度优先搜索的基本原则：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到满足条件的目标为止。4/34•然而要实现这样的算法，我们需要用到编程的一大利器---递归。•讲一个更具体的例子：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：…………。好家伙，这样讲到世界末日还讲不玩，老和尚讲的故事实际上就是前面的故事情节，这样不断地调用程序本身，就形成了递归。万一这个故事中的某一个老和尚看这个故事不顺眼，就把他要讲的故事换成：“你有完没完啊！”，这样，整个故事也就嘎然而止了。•我们编程就要注意这一点，在适当的时候，就必须要有一个这样的和尚挺身而出，把整个故事给停下来，或者说他不再往深一层次搜索，要不，我们的递归就会因计算机栈空间大小的限制而溢出，称为stackoverflow。5/34•顺序按数字编号顺序先后访问。那么我们怎么来保证这个顺序呢？基本思想：从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，…，一直进行下去，直到找到目标状态G为止。6/34Booleanvisited[MAX];Status(*VisitFunc)(intv);//顶点的访问函数voidDFSTraverse(graphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;vG.vexnum;++v)visited[v]=FALSE;for(v=0;vG.vexnum;++v)if(!visited[v])DFS(G,v);}voidDFS(GraphG,intv){visited[v]=TRUE;VisitFunc(G.vertices[v].data);for(w=FirstAdjvex(G,v);w;w=NextAdjvex(G,v,w))if(!visited[w])DFS(G,w);}7/34马的走法1、问题描述在一个4×5的棋盘上，马的起始位置坐标(纵，横)位置由键盘输入，求马能返回初始位置的所有不同走法的总数(马走过的位置不能重复，马走“日”字)。输入输出样例：8/342、问题分析由于4×5的棋盘的问题规模比较小，用回溯法可以较好的解决问题。如下图所示，如果从(1,1)出发，那么马首先从(1,1)点走向(3,2)点，再到(2,4)点，这样过程可以一步一步递推下去，最后要么找到一条路径，要么进入“死胡同”，这时函数find(p1,p2)就不能递归调用自己了，因此实现了回溯。为了避免走重复的位置，可以定义一个数组chess[5][4]表示棋盘，若chess[i][j]=1，则表示马已经走过，在递推时就不能走此位置，应该换一个方向。对于马走的方向，可以定义数组d[2][8]，每列表示一个马可以走的方向。9/343、参考代码#includestdio.hintchess[5][4];intd[2][8]={{-1,-1,-2,-2,2,2,1,1},{2,-2,1,-1,1,-1,2,-2}};intsx,sy,tot;voidfind(intp1,intp2){inti,pi,pj;for(i=0;i8;i++){pi=p1+d[0][i];pj=p2+d[1][i];if((pi==sx)&&(pj==sy))//一定要放在前面tot++;elseif((pi=0)&&(pi5)&&(pj=0)&&(pj4)&&(chess[pi][pj]==0)){chess[pi][pj]=1;find(pi,pj);chess[pi][pj]=0;}}}10/34intmain(void){inti,j;while(scanf(%d%d,&sy,&sx)==2){for(i=0;i5;i++)for(j=0;j4;j++)chess[i][j]=0;tot=0;sx--;sy--;find(sx,sy);printf(%d\n,tot);}return0;}3、参考代码11/34水仙花数•一个三位数abc如果满足abc=a^3+b^3+c^3那么就把这个数叫做水仙花数。•如果一个N位数所有数码的N次方的和加起来等于这个数字本身，我们把这样的数叫做广义水仙花数，容易看出来N=3是广义水仙花数。•现在，我们的任务是，输入一个m(m7)，让你求出所有满足N=m的广义水仙花数。•3(153370371407)•5(547489272793084)12/34•方法：数据规模很小，可以直接枚举所有情况，然后判断是否满足条件。•难点：循环层数不确定•怎么实现这个m重循环？•答案：递归。13/34m重循环的实现：voiddfs(intdeep){if(deepm){//checkanswer}elseif(deep=m){for(i=1;i=n;i++)dfs(deep+1);}}14/34#includeiostream#includecstdiousingnamespacestd;intm;intPow(intx,intn){intres=1;while(n--)res*=x;returnres;}15/34voiddfs(intdeep,intcurNum,intcurSum){if(deepm)//类似于basecase{if(curNum==curSum)printf(%d\n,curNum);}elseif(deep=m){intstart=(deep==1);//第一位不为0for(inti=start;i=9;i++)dfs(deep+1,curNum*10+i,curSum+Pow(i,m));//缩小问题规模}}16/34intmain(){while(scanf(%d,&m)==1){dfs(1,0,0);}return0;}17/34深度优先搜索解决问题的框架voiddfs(intdeep,StatecurState){if(deepMax)//深度达到极限{if(curState==target)//找到目标{//...}}else{for(i=1;i=totalExpandMethod;i++){dfs(deep+1,expandMethod(curState,i));}}}18/34大逃亡=1022•Descriptionlove8909遇到危险了！！！他被困在一个迷宫中，彷徨而无助。现在需要你来帮助他走出困境。他只能记住指定长度的指令(指令的长度由MinLen和MaxLen限定)，并循环执行，而且他只会向下或向右（很奇怪吧^_^）。他在地图的左上角，你需要告诉他一个运动序列，即向下（D）或向右（R），使他能够成功走出这个图且不碰到陷阱。如果还不明白，可以参看图片。图片1,2对应样例的第1组，图片3对应样例的第2组。19/34•Input第一行为1个整数T，表示有T组测试数据第二行为4个整数Height,Width,MinLen,MaxLen，分别表示地图的高，宽，命令序列的最小和最大长度。3=Height,Width=60,2=MinLen=MaxLen=35第三行至第Height+2行为地图信息。其中'.'表示空地，'X'表示陷阱。•Output只有一行，为命令序列（只含D,R）。注意：如果有多解，输入命令长度最短的；依然有多解，输出字典序最小的（D的字典序比R小），数据保证一定存在一组解。字典序：字符串从前往后依次比较，第一个字符不同的位置，字符较小的字符串字典序较小，详情参见字典。20/34•SampleInput23322.X....X..5523..X.X....X......XX..XX..X•SampleOutputDRDRR21/34•方法：暴力•复杂度为O(2^L)，L是序列长度•仔细思考之后会发现，人的活动范围与D和R的顺序无关。•即当D和R的个数确定以后，他的活动范围一定在若干个首尾相接（左上角和右下角相连）的矩形内。•这样，我们枚举序列中D和R的个数，然后将各个将要经过的矩形并起来，组成一个新的矩形，若这个矩形从左上角至右下角可达，则有解。22/34#includeiostream#includecstdiointHeight,Width,MinLen,MaxLen,sH,sW;charMAP[64][64];boolin(intx,inty){returnx=0&&xHeight&&y=0&&yWidth;}boolcheck(intx,inty){while(in(x,y)){if(MAP[x][y]=='X')returnfalse;x+=sH;y+=sW;//与while配合确保重复执行不会遇障碍}returntrue;}参考程序23/34charres[128];booldfs(intx,inty,intD,intR){if(check(x,y)==false)returnfalse;if(D==0&&R==0){res[x+y]='\0';printf(%s\n,res);returntrue;}if(D0)//由于字典序，先考虑向下再考虑向右{res[x+y]='D';if(dfs(x+1,y,D-1,R))returntrue;}if(R0){res[x+y]='R';if(dfs(x,y+1,D,R-1))returntrue;}returnfalse;}24/34intmain(){intT;scanf(%d,&T);while(T--){scanf(%d%d%d%d,&Height,&Width,&MinLen,&MaxLen);for(inti=0;iHeight;i++)scanf(%s,MAP[i]);boolfind=false;for(intL=MinLen;!find&&L=MaxLen;L++)for(sH=L;!find&&sH=0;sH--)find=dfs(0,0,sH,sW=L