浅谈DFS

引领天下 · 2018-07-22 17:26:24 · 个人记录

DFS，即深度优先搜索，是一种很常见但并不难的算法，可以用来解决很多东西。就像 n^{3} 的暴力无所不能一样我们来谈一谈它的优化和结构吧！

DFS函数一般由边界条件、主体和递归组成，我们来挨个探讨一下

1.边界条件

DFS中的边界条件有很多，例如对一个m位的数组填数字时填到m+1位啦，找一个连续的正整数序列时碰到0啦，等等。但它们的共同作用是让函数递归结束，返回上一层。

在第一种情况中，（即对一个m位的数组填数字时填到m+1位），可以考虑更新答案（就是我们dfs的目的），但有时也是输出一个序列（例：P1706）。这时，我们需要在回溯之前更新，防止未更新就返回了

伪代码：

if 边界条件 {更新（或输出）;回溯;}

2.主体

这就是一个函数的主要部分了，通常就是递归部分，但在部分题目中在递归前需要对某些值进行预处理。

3.递归

这是一个函数最重要的部分，它写的好坏决定了dfs的效率，递归的基本原则希望大家记住：递归前改的值，递归后一定要改回去！

我们假定我们需要找到 6 这个数，在图中，我们并不需要优化；但如果有1000000，10000000个节点呢？这样朴素的算法岂不会超时？

于是，优化应运而生。

• 优化1：剪枝

  剪枝有多种方法，我来介绍主要的几种。

  • 1.修改判断策略

    不难看出，对于刚才的树，如果我们在搜索中加上一个限制条件<=6，那么7节点就不会搜索。在此例中，我们只剪掉了一个节点；但如果7是一棵很大的子树呢？那么我们的dfs就会快很多。

  • 2.记忆化

    这也是一种剪枝，是最经典的以空间换时间，即将每次搜索的结果记下来保存进一个数组，下次搜到同一节点时就不必再搜了，直接读取已有的答案即可。

  • 3.最优性剪枝

    如果当前答案已经不如最优解，那么就没有必要搜下去了。

    在此例中没有体现，但如果是一个有n堆书、在搬完一堆上第一本后才能搬第二本，求最少的力气的题目中，如果当前的力气已经超过了答案，那就没有必要找下去了。

  • 4.剪枝的原则

    主要有以下几个原则：

    • 1.正确性

      我们不能把长有答案的枝条也剪了，不然dfs就不对了。（在本例中不能剪去3的子树）

    • 2.准确性

      即尽可能多地剪去不必要的枝条。比如，本例中，如果已经知道4的子树上没有6这个数，那么就可以毫不犹豫地把4的子树剪掉。

    • 3.高效性

      在写剪枝策略的时候，我们还要考虑判断本身的复杂度；如果判断本身很慢，那就反而会得不偿失。比如，为了剪一个 O(n) 的枝条，你写了个 O(n^{2}) 的判断，还不如不写。

• 优化2：优化搜索顺序

  在有些题目中，优化搜索顺序可以大幅度提高程序运行速度。在有的题目中，从根节点出发可能搜不到答案；从叶节点出发，反而可能得到答案。

  在本例中，如果我们从3节点开始搜，那么1的子树再大我们也不怕了：因为答案6已经在第一次搜索中找到了。

• 优化3：排除等效兀余

  如果搜3枝条和搜2枝条是一个效果，那么我们就可以将其中一条剪去只搜另一条。比如，如果搜3的子树需要 O(log n) ，而搜2的子树需要 O(n) ，且已知搜3和2是一个效果，那么我们就会剪掉2的子树去搜3。

• 优化4：输入输出优化

  对于这个是题目就能用的优化，我不作多解释。

在有了这些优化后，你的dfs一定会很快的！（不过如果不是dfs能跑的常数你非要跑kkk也救不了你）