yltx's blog

yltx's blog

Κοιτάζοντας πάνω στον έναστρο ουρανό, κάτω στη γη.

浅谈DFS

posted on 2018-07-22 17:26:24 | under 日报、算法 |

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也救不了你)