浅谈DFS

DFS，即深度优先搜索，是一种很常见但并不难的算法，可以用来解决很多东西。~~就像 $ n^{3} $ 的暴力无所不能一样~~我们来谈一谈它的优化和结构吧！ DFS函数一般由边界条件、主体和递归组成，我们来挨个探讨一下 # 1.边界条件 DFS中的边界条件有很多，例如对一个m位的数组填数字时填到m+1位啦，找一个连续的正整数序列时碰到0啦，等等。但它们的共同作用是让函数递归结束，返回上一层。 在第一种情况中，（即对一个m位的数组填数字时填到m+1位），可以考虑更新答案（就是我们dfs的目的），但有时也是输出一个序列（例：P1706）。这时，我们需要在回溯之前更新，防止未更新就返回了 伪代码： ```cpp 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也救不了你）