当前位置: 首页 > 工具软件 > dfs > 使用案例 >

DFS详述

申博厚
2023-12-01

一、算法思想

  如算法名称那样,深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是:为了求得问题的解,先选择某一种可能情况向前(子结点)探索,在探索过程中,一旦发现原来的选择不符合要求,就回溯至父亲结点重新选择另一结点,继续向前探索,如此反复进行,直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。   由此可见,把通常问题转化为树的问题是至关重要的一步,完成了树的转换基本完成了问题求解。

深度优先搜索的优化

  1、优化思想  

                减少所遍历的状态总数

  2、三种方法  

    (1)减少节点数   思想:尽可能减少生成的节点数   

     (2)定制回溯边界   

       思想:定制回溯边界条件,剪掉不可能得到最优解的子树  

   在很多情况下,我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解,搜索到后也只能回溯。      为了避免出现这种情况,我们需要灵活地去定制回溯搜索的边界。   在深度优先搜索的过程当中,往往有很多走不通的“死路”。假如我们把这些“死路”排除在外,不是可以节省很多的时间吗?打一个比方,前面有一个路径,别人已经提示:“这是死路,肯定不通”,而你的程序仍然很“执着”地要继续朝这个方向走,走到头来才发现,别人的提示是正确的。这样,浪费了很多的时间。针对这种情况,我们可以把“死路”给标记一下不走,就可以得到更高的搜索效率。

   (3)记忆化  

  思想:运用记忆化的方法,使得一些遍历过的子树不要重复遍历   

   3、三个原则  

 (1)正确性:剪去的“枝条”不包含最优答案;  

 (2)准确性:在保证第一条原则的情况下,尽可能的剪去更多不包含最优答案的枝条;  

 (3)高效性:通过剪枝要能够更快的接近到达最优解。 

  

******************深度优先搜索 (Depth-First Traversal)***************
深度优先搜索的思想是尽可能深的搜索图,在<<算法艺术与信息学竞赛>>一书中提到:随机搜索就像是在慌乱之中找东西,因为你并不知道东西在哪,广度优先搜索则像是你的眼镜掉在地上之后,你肯定会先摸最近的一片区域,而深度优先搜索则像你在走迷宫,你不可能有分身术同时站在每一个点上,只能沿着一条路走到底,如果碰壁了,则退回来再搜索下一个可能的路径.深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。
例如对于以下一个树:
          1
        2   3
      4   5   6
深度优先的策略是1->2->4->退后一步->5->退后一步->退后一步->3->6->结束
而广度优先则是第一次:1->2->3第2次:4->5->6

从深度优先的策略上看就知道深搜一般是用递归来实现;深度优先搜索的框架很简单:
void Dfs ( int n )
{
     if ( 满足结束条件,即搜索到终点 )
         return ;
     else
         Dfs ( n + 1 );
}
深搜的框架是如此简单,但是它可能有很多变种,一般用来搜索图

转载于:https://www.cnblogs.com/FCWORLD/archive/2010/11/12/1875507.html

 类似资料: