《深度优先搜索ppt课件.ppt》由会员分享，可在线阅读，更多相关《深度优先搜索ppt课件.ppt（35页珍藏版）》请在三一办公上搜索。
1、第八讲,搜索专题 深度优先（DFS）,ACM算法与程序设计,数学科学学院：汪小平,深度优先搜索算法（Depth-First-Search）,DFS是由获得计算机领域的最高奖-图灵奖的霍普克洛夫特与陶尔扬发明DFS是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。DFS的时间复杂度不高（为线性时间复杂度），遍历图的效率往往非常高。因此
2、，鉴于深度优先搜索算法的强大功能以及高效性往往被研究图论问题的专家所推崇。时间复杂度：O(bm)；空间复杂度：O(bm)；b-分支系数m-图的最大深度,迷宫问题,首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出口出来。那老鼠会怎么走？当然可以是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意选择其中的一条继续往下走，如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去，如果遇到了出口，老鼠的旅途就算成功结束了。深度优先搜索的基本原则：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到满足条件
3、的目标为止。,然而要实现这样的算法，我们需要用到编程的一大利器-递归。讲一个更具体的例子：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：。好家伙，这样讲到世界末日还讲不玩，老和尚讲的故事实际上就是前面的故事情节，这样不断地调用程序本身，就形成了递归。万一这个故事中的某一个老和尚看这个故事不顺眼，就把他要讲的故事换成：“你有完没完啊！”，这样，整个故事也就嘎然而止了。我们编程就要注意这一点，在适当的时候，就必须要有一个这样的和尚挺身而
4、出，把整个故事给停下来，或者说他不再往深一层次搜索，要不，我们的递归就会因计算机栈空间大小的限制而溢出，称为stack overflow。,顺序按数字编号顺序先后访问。那么我们怎么来保证这个顺序呢？,基本思想：从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退
5、到上层节点，扩展可能的分支生成新状态，一直进行下去，直到找到目标状态G为止。,Boolean visitedMAX;Status(*VisitFunc)(int v);/顶点的访问函数void DFSTraverse(graph G,Status(*Visit)(int v)VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);void DFS(Graph G,int v)visitedv=TRUE;VisitFunc(G.verticesv.data);fo
6、r(w=FirstAdjvex(G,v);w;w=NextAdjvex(G,v,w)if(!visitedw)DFS(G,w);,马的走法,1、问题描述,在一个45的棋盘上，马的起始位置坐标(纵，横)位置由键盘输入，求马能返回初始位置的所有不同走法的总数(马走过的位置不能重复，马走“日”字)。输入输出样例：,2、问题分析,由于45的棋盘的问题规模比较小，用回溯法可以较好的解决问题。如下图所示，如果从(1,1)出发，那么马首先从(1,1)点走向(3,2)点，再到(2,4)点，这样过程可以一步一步递推下去，最后要么找到一条路径，要么进入“死胡同”，这时函数find(p1,p2)就不能递归调用自己了
7、，因此实现了回溯。,为了避免走重复的位置，可以定义一个数组chess54表示棋盘，若chessij=1，则表示马已经走过，在递推时就不能走此位置，应该换一个方向。对于马走的方向，可以定义数组d28，每列表示一个马可以走的方向。,3、参考代码,#include int chess54;int d28=-1,-1,-2,-2,2,2,1,1,2,-2,1,-1,1,-1,2,-2;int sx,sy,tot;void find(int p1,int p2)int i,pi,pj;for(i=0;i=0),int main(void)int i,j;while(scanf(%d%d,3、参考代码,水
8、仙花数,一个三位数abc如果满足abc=a3+b3+c3 那么就把这个数叫做水仙花数。如果一个N位数所有数码的N次方的和加起来等于这个数字本身，我们把这样的数叫做广义水仙花数，容易看出来N=3是广义水仙花数。现在，我们的任务是，输入一个m(m 7)，让你求出所有满足N=m的广义水仙花数。3(153 370 371 407)5(54748 92727 93084),方法：数据规模很小，可以直接枚举所有情况，然后判断是否满足条件。难点：循环层数不确定怎么实现这个m重循环？答案：递归。,m重循环的实现：void dfs(int deep)if(deep m)/check answerelse if(
9、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=9;i+
10、)dfs(deep+1,curNum*10+i,curSum+Pow(i,m);/缩小问题规模,int main()while(scanf(%d,深度优先搜索解决问题的框架,void dfs(int deep,State curState)if(deep Max)/深度达到极限 if(curState=target)/找到目标/.else for(i=1;i=totalExpandMethod;i+)dfs(deep+1,expandMethod(curState,i);,大逃亡http:/,Description love8909遇到危险了！他被困在一个迷宫中，彷徨而无助。现在需要你来帮助他
11、走出困境。他只能记住指定长度的指令(指令的长度由MinLen和MaxLen限定)，并循环执行，而且他只会向下或向右（很奇怪吧_）。他在地图的左上角，你需要告诉他一个运动序列，即向下（D）或向右（R），使他能够成功走出这个图且不碰到陷阱。如果还不明白，可以参看图片。图片1,2对应样例的第1组，图片3对应样例的第2组。,Input 第一行为1个整数T，表示有T组测试数据第二行为4个整数Height,Width,MinLen,MaxLen，分别表示地图的高，宽，命令序列的最小和最大长度。3=Height,Width=60,2=MinLen=MaxLen=35第三行至第Height+2行为地图信息。其
12、中.表示空地，X表示陷阱。Output 只有一行，为命令序列（只含D,R）。注意：如果有多解，输入命令长度最短的；依然有多解，输出字典序最小的（D的字典序比R小），数据保证一定存在一组解。字典序：字符串从前往后依次比较，第一个字符不同的位置，字符较小的字符串字典序较小，详情参见字典。,Sample Input 23 3 2 2.X.X.5 5 2 3.X.X.X.XX.XX.XSample Output DRDRR,方法：暴力复杂度为O(2L)，L是序列长度 仔细思考之后会发现，人的活动范围与D和R的顺序无关。即当D和R的个数确定以后，他的活动范围一定在若干个首尾相接（左上角和右下角相连）的矩
13、形内。这样，我们枚举序列中D和R的个数，然后将各个将要经过的矩形并起来，组成一个新的矩形，若这个矩形从左上角至右下角可达，则有解。,#include#include int Height,Width,MinLen,MaxLen,sH,sW;char MAP6464;bool in(int x,int y)return x=0,参考程序,char res128;bool dfs(int x,int y,int D,int R)if(check(x,y)=false)return false;if(D=0,int main()int T;scanf(%d,作业：与大逃亡很相似的题目Tempter
14、of the Bone http:/,Restore Equationshttp:/,Description An 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 so
15、me digits are missing because of the eroding power of Mars nature.Here is one example.,Description An 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.How
16、ever 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 intelle
17、ctual 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,y
18、ou 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
19、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 b
20、e 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 is greater than zero.At least one*will be present in e
21、ach equation.,Sample Input 2 12*45*5*5 11 11*121Sample Output Yes No,枚举两个乘数再检查是否满足等式。递归搜索完成这个题目和Google Code Jam China 2006 第二轮的500分类似。,#include#include#include/算法头文件调用reverse算法 stringA,B,C;intlena,lenb,lenc;inta3,b3;boolflag=false;intmain()intncase;scanf(%d,voidcheck()intx=a0+a1*10+a2*100;inty=b0+b1
22、*10+b2*100;intz=x*y;for(inti=0;i=10)return;if(z=Clenc-1-0|Clenc-1=*)flag=true;,voiddfs1(intn)/针对第二个乘数进行深度搜索 if(flag)return;if(n=lenb)check();return;if(Bn=*)for(intj=(n=lenb-1);j=9;+j)bn=j;dfs1(n+1);else bn=Bn-0;dfs1(n+1);,voiddfs(intn)/针对第一个乘数进行深度搜索if(flag)return;if(n=lena)dfs1(0);return;if(An=*)for
23、(intj=(n=lena-1);j=9;+j)an=j;dfs(n+1);else an=An-0;dfs(n+1);,课程成绩考核评定标准,一、成绩构成1、平时成绩：30%2、期末论文：70%二、平时成绩构成：1、参与校赛与平时OJ练题：20%3、平时出勤：10%三、期末论文类型及要求 论文格式要求 需选择某一专题的深入研究 如：线段树、树状数组，网络流等等，可以自己任意选择，题目范围涉及各个算法方面。要求：要有该专题的理论描述，自己完成的典型题目，并对题目给出解题分析和实现代码（需加注释），选题要有新意，有一定难度。四、课件下载邮件及密码Email：UESTCACM Password：123666五、论文交付电子文档请发送到，纸质文档交付时间与地点为：第12、13周星期二晚A402，第14、15、16周星期二晚科研楼A227。若有改变或其它通知，将公布在UESTCACM。,
