Question

什么是深度优先搜索？

Answer 1

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。由此可见，把通常问题转化为树的问题是至关重要的一步，完成了树的转换基本完成了问题求解。
(1)减少节点数，思想：尽可能减少生成的节点数
(2)定制回溯边界，思想：定制回溯边界条件，剪掉不可能得到最优解的子树
在很多情况下，我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解，搜索到后也只能回溯。为了避免出现这种情况，我们需要灵活地去定制回溯搜索的边界。在深度优先搜索的过程当中，往往有很多走不通的“死路”。假如我们把这些“死路”排除在外，不是可以节省很多的时间吗？打一个比方，前面有一个路径，别人已经提示：“这是死路，肯定不通”，而你的程序仍然很“执着”地要继续朝这个方向走，走到头来才发现，别人的提示是正确的。这样，浪费了很多的时间。针对这种情况，我们可以把“死路”给标记一下不走，就可以得到更高的搜索效率。