一、算法思想
如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。 由此可见，把通常问题转化为树的问题是至关重要的一步，完成了树的转换基本完成了问题求解。
深度优先搜索的优化
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 );
}
深搜的框架是如此简单,但是它可能有很多变种,一般用来搜索图