深搜,顾名思义,是深入其中、直取结果的一种搜索方法。
如果深搜是一个人,那么他的性格一定倔得像头牛!他从一点出发去旅游,只朝着一个方向走,除非路断了,他绝不改变方向!除非四个方向全都不通或遇到终点,他绝不后退一步!因此,他的姐姐广搜总是嘲笑他,说他是个一根筋、不撞南墙不回头的家伙。
深搜是这样跟姐姐讲的:关于旅行呢,我并不把目的地的风光放在第一位,而是更注重于沿路的风景,所以我不会去追求最短路,而是把所有能通向终点的路都走一遍。可是我并不知道往哪走能到达目的地,于是我只能每到一个地方,就向当地的人请教各个方向的道路情况。为了避免重复向别人问同一个方向,我就给自己规定1 :先问北,如果有路,那就往北走,到达下一个地方的时候就在执行此规定,如果往北不通,我就再问西,其次是南、东,要是这四个方向都不通或者抵达了终点,那我回到上一个地方,继续探索其他没去过的方向。我还要求自己要记住2 那些帮过他的人,但是那些给我帮倒忙的、让我白费力气的人,要忘记3他们。有了这些规定之后,我就可以大胆的往前走了,既不用担心到不了不目的地,也不用担心重复走以前的路。哈哈哈……
优点
1、能找出所有解决方案;
2、优先搜索一棵子树,然后是另一棵,所以和广搜对比,有着内存需要相对较少的优点;
缺点
1、要多次遍历,搜索所有可能路径,标识做了之后还要取消;
2、在深度很大的情况下效率不高;
void DFS() //N代表目前DFS的深度 { if(找到解) //进行相应的操作 { … return; } for(inti=0;i<4;i++) //枚举四个方向 { DFS(N+1); //进入下层递归 } }
广搜,顾名思义,是多管齐下、广撒网的一种搜索方法
如果广搜是一个人,那么她一定很贪心,而且喜新厌旧!她从一点出发去旅游,先把与起点相邻的地方全部游览一遍,然后再把与她刚游览过的景点相邻的景点全都游览一遍……一直这样,直至所有的景点都游览一遍。
广搜属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
类似树的按层遍历,其过程为:首先访问初始点Vi,并将其标记为已访问过,接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2…Vit,并均标记为已访问过,然后再按照Vi1、Vi2…Vit 的次序,访问每一个顶点的所有未被访问过的邻接点,并均标记为已访问过,依此类推,直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。
优点
1、对于解决最短或最少问题特别有效,而且寻找深度小;
2、每个结点只访问一遍,结点总是以最短路径被访问,所以第二次路径确定不会比第一次短;
缺点
1、内存耗费量大(需要开大量的数组单元用来存储状态);
void BFS() { … …//初始化起点入队 while(!q.empty()) //判断队是否为空 { … …//获取队首元素 if(... …){… …}//判断是否是终点 for(int i=0;i<4;i++)//四个方向 { k.x=p.x+dir[i][0]; k.y=p.y+dir[i][1]; //向各个方向走一步 if(judge())//判断能不能走 { … …//各种处理 vis[k.x][k.y]=1; //标记 q.push(k); //入队 } } } }
广搜打印路径:虽然它有多个后继结点,但前驱节点只有一个。所以可以逆向打印路径,即从终点出发找通向起点的路径。
遍历四个方向
标记,标识已经走过的结点
取消标记
1 深度(Depth)优先搜索DFS:一个递归过程,有回退过程。尽可能“深”地搜索图。在深度优先搜索中,对于最新发现的顶点,如果它还有以此为起点而未探测到的边,就沿此边继续搜索下去。当结点V的所有边都已被探寻过,搜索将回溯到发现结点V有那条边的始结点,则选择其中一个作为源结点并重复以上过程,整个进程反复进行直到所有结点都被发现为止。
2 广度(Breath)优先搜索BFS:一个分层的搜索过程,没有回退过程,是非递归的。只是每次都尽可能地扩展当前节点的邻居节点,之后再向其子结点进行扩展。
BFS 常用于找单一的最短路线,它的特点是 “搜到就是最优解”,而 DFS 用于找所有解的问题,它的空间效率高,而且找到的不一定是最优解,必须记录并完成整个搜索,故一般情况下,深搜需要非常高效的剪枝。
BFS:对于解决最短或最少问题特别有效,而且寻找深度小,但缺点是内存耗费量大(需要开大量的数组单元用来存储状态)。
DFS:对于解决遍历和求所有问题有效,对于问题搜索深度小的时候处理速度迅速,然而在深度很大的情况下效率不高。
深度优先搜索用栈(stack)来实现,整个过程可以想象成一个倒立的树形:
1、把根节点压入栈中。
2、每次从栈中弹出一个元素,搜索所有在它下一级的元素,把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。
4、如果遍历整个树还没有找到,结束程序。
当然DFS也可以直接利用函数进行递归。
广度优先搜索使用队列(queue)来实现,整个过程也可以看做一个倒立的树形:
1、把根节点放到队列的末尾。
2、每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3、找到所要找的元素时结束程序。
4、如果遍历整个树还没有找到,结束程序。
BFS根据实际情况可能要用到优先队列。
本页共86段,2985个字符,6963 Byte(字节)