目录

---

---

第一章 引言

$1.1$ DFS 的定义

• DFS 的基层实现原理
• DFS 的实现场景
• DFS 的实现方式
• 回溯法的原理

$1.2$ DFS 的可传递信息

• DFS 自底向上的信息维护

$1.3$ DFS 的铺垫知识

• 前提条件
• 变换步骤（递归）
• DFS 的三种枚举方式

$1.4$ 记忆化搜索初步

第二章 DFS 题目的状态空间与转换

$2.1$ DFS 在地图类问题的转换

• DFS 维护连通块
• DFS 有约束的跑图问题
• DFS 解决棋盘类问题

$2.2$ DFS 搜索最优解

$2.3$ DFS 搜索最优方案路径

$2.4$ DFS 搜索方案数

第三章 DFS 题目的复杂度优化

$3.1$ DFS 剪枝

$3.2$ DFS 记忆化搜索

$3.3$ DFS 启发式搜索

• 估价函数的设计
• 估价函数的使用方式

第四章 DFS 树与图上应用

$4.1$ DFS 信息传递

$4.2$ DFS 信息维护

• 整体思想
• 特殊性质

$4.3$ 基于 DFS 的算法

• tarjan 算法

第五章 随机化-模拟退火

---

正文篇

---

---

第一章 引言

---

$1.1$ DFS 的定义

* DFS 的基层实现原理

$DFS$ 即 深度优先搜索，在程序中是以 栈的形式 实现，符合 栈 的先进先出的原理，当栈不为空时，就会一直弹出栈顶元素。

这也是 $DFS$ 在实现时，会一直往一条道上搜， 直到搜完才返回的原因。

但是，如果 $DFS$ 在第一次搜完之后就结束了， 那么作用不大，但是如果在 每一次递归 (即压栈) 的时候

同时递归其它值， 由于递归其它值的操作只有在 上一条道搜完之后 才会执行，所以会在一些深度上形成分叉。

只要能够 确认问题的搜索框架，就可以 穷举所有方案，也就是 一切皆可搜 的由来。

* DFS 的实现场景

$DFS$ 是一种用递归实现的算法，但本质上完全可以借助栈来解决。

常见的深度优先搜索的应用分别是 图的连通性模型、枚举方案数、枚举所有可能性、 树的自底向上维护信息 等等，

这些都会在后文作详细介绍。

* DFS 的实现方式

那 $DFS$ 又应该如何实现呢？

其中的难点在于对题目要求的转换和对无用的状态空间的排除，

在此，给出一些最基本的 $DFS$ 代码实现和最基本的思想讲解。

设计一个 $DFS$ 代码，你要确定在你的搜索树中你要 维护那些信息，以及你往下搜索的扩展方式。

一定要尽量吝啬于你 往外延伸的分支数量，不然时间复杂度会以一个极为恐怖的方式增长。

void dfs(变化的参数, 如深度、方案数、枚举到第几个方案、横纵坐标等等)
{
    if 问题边界                 // 必备的, 只有有限的空间才可以搜索
    {
        维护答案;
        return;
    }

    往不同方向搜索延伸          // 搜索分支
    {
        dfs(参数发生不同的变化);   // 往下搜索 
    }
}

这是一个最基本的框架，也是后文延伸的一个基础，抱着循序渐进的想法，更多内容就留给下文阐述。

* 回溯法的原理

回溯法 是系统地搜索问题状态的方法。

某个问题的 所有可能状态 称为问题的 状态空间，若 状态空间是有限的，便可将状态空间映射成 树结构。

请记住，任何状态空间可以映射成树结构的问题，都可以使用回溯法。

也就是说，回溯法是能够在树结构里搜索到 通往特定终点 的一条或者多条特定路径。

回溯算法的基本思想是：

"从一条路往前走，能进则进，不能进则退回来，换一条路再试，从而搜索到抵达特定终点的一条或者多条特定路径。"

值得注意，回溯法以深度优先搜索的方式搜索 状态空间，并且在搜索过程中 用剪枝函数避免无效搜索。

那么，它可以解决哪些题目呢？

1. 【组合问题】：N个数里面按一定规则找出k个数的集合

2. 【排列问题】：N个数按一定规则全排列，有几种排列方式

3. 【切割问题】：一个字符串按一定规则有几种切割方式

4. 【子集问题】：一个N个数的集合里有多少符合条件的子集

5. 【棋盘问题】：N皇后，解数独等等

在回溯法的题目里，我们的模板也有了一些变化。

void dfs(变化的参数, 如深度、方案数、枚举到第几个方案、横纵坐标等等)
{
    if 问题边界                 // 必备的, 只有有限的空间才可以搜索
    {
        维护答案;
        return;
    }

    往不同方向搜索延伸          // 搜索分支
    {
        处理此节点信息
        dfs(参数发生不同的变化);    // 往下搜索
        复原此节点信息, 才可以进行对分支的正确搜索。    // 回溯
    }
}

为什么这样就可以遍历整个搜索树呢？

感性的理解是：for循环可以理解是横向遍历，dfs（递归）就是纵向遍历

同样，也可以画图体会。

多数问题都需要靠回溯法来求解，但必须要强调的是

深度优先搜索 不等于 回溯法

正如上文所述，回溯法解决的是 树形结构 问题，

而深度优先搜索同样也可以用于 图结构 问题

当问题不在只是一棵树的时候，可能会存在 例如 环、重边 等更复杂的结构。

更重要的是这类问题 一个节点需要且只需访问一次。

为了解决重复遍历的问题，我们往往会用一个 $st$ 数组来储存图的某个节点是否重复遍历的问题。

而不再继续使用回溯法了，毕竟你要走的路径已经给出了呀。

---

$1.2$ DFS 的可传递信息

*DFS 自底向上的信息维护

深搜作为一种实用的算法，可以维护几乎所有的信息，但笔者能力有限，故此，仅列举几种常用信息的维护方式。

$【sum$ 值的维护】 ：

我们用一个 $sum$ 数组储存 以这个节点为根的子树之和，同时用一个 $st$ 数组储存 树的某个节点是否被重复遍历。

然后，我们就可以遍历整棵树了。

可以看出，从一个节点出发往下的所有节点都是它的子树。

因此，我们仅需要在往下搜索时，储存一个变量 $sum$, 在返回的过程中维护以它为根的子树之和，往上传递时，其父节点仅需要加上它的值就可以了。

这也是一个名为 打包 的重要思想。

【树的最小字典序维护】 ：

给定你一颗树，让你求出在可以重复经过同一个节点的情况下，遍历所有节点的字典序最小的方案是什么？

字典序仅会在第一次到达此节点时累计。

我们用一个 $path$ 数组储存方案，先将每一个点的出边排序，从字典序小的边开始搜，并维护第一次搜到的点的方案。

同样用 $st$ 数组判重，由于 DFS 一次搜到底的性质，在不存在环的情况下满足

运用贪心的思想，由字典序从小到大遍历整棵树，一点是最优的。

【树的重心】 ：

重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中子节点数的最大值最小，那么这个节点被称为树的重心。

将一颗树的一个节点删掉后，树会被分成两个部分，可维护的值有两个。

一个是以它为根的下一层子树中最大的一颗的子节点数，一个是除去以它为根的子树后剩余节点数。

根据容斥原理，直接维护最大联通子图的节点数即可。

---

$1.3$ DFS 的铺垫知识

*前提条件

当 原问题 与 问题边界 之间的 每个变换步骤具有相似性时 就可以考虑用 递归 或 递推 来求解

*变换步骤（递归）

对于递归算法，可以通过以下三个操作来求解

---

1. 【自身调用自身】

缩小问题规模空间 ，

这意味着程序尝试寻找在 原问题 与 问题边界 之间的 变化路线，并向 正在探索 的路线上迈出一步

2. 【回溯时还原现场（搜索失败）】

尝试求解 规模缩小以后的问题，

如果失败，程序需要 重新回到当前问题 去寻找 其它的变换路线，

因此把 当前问题 缩小为 子问题 时所做的 对当前问题状态产生影响的事情 应 全部失效

3. 【扩展（搜索成功）】

找到了 规模缩小以后的问题 的答案， 那么将答案 扩展到当前问题。

如果失败，就 重新返回 当前问题，继续寻找 当前答案 的 其它变换路线，直至 确定当前问题无法求解

---

总结

简洁的说，就是 缩小，求解，扩展

---

*DFS 的三种枚举方式

【指数型枚举】 ：

对于序列中每个整数都有两种可能，选 或者 不选

也就是说，这颗搜索树上的每一个节点都有两个分支，

每次将尚未确定的整数减少 $1$，从而转换成一个更小的同类问题。

注意：指数型枚举不考虑顺序

时间复杂度 $O(k^n)$

注意：其中的 $k$ 为常数。

void dfs(int u){
    if (u == n + 1)
    {
        for (int i = 0; i < ch.size(); i ++ )
            printf("%d ", ch[i]);
        puts("");
        return;
    }

    dfs(u + 1);
    ch.push_back(u);

    dfs(u + 1);
    ch.pop_back();
}

【组合型枚举】 ：

可以等价于上述枚举仅在 枚举数 $= m$ 的情况下有效。

注意：组合型枚举不考虑顺序

时间复杂度 $O(C_n^m)$

组合数的知识会在 数论 一章进行讲解

void dfs(int u){
    if (ch.size() > m || ch.size() + (n - u + 1) < m) return;
    if (u == n + 1)
    {
        for (int i = 0; i < ch.size(); i ++ )
            printf("%d ", ch[i]);
        puts("");
        return;
    }

    dfs(u + 1);
    ch.push_back(u);

    dfs(u + 1);
    ch.pop_back();
}

【排列型枚举】 ：

它与组合型枚举的最大不同在于它考虑搜索顺序。

它的搜索树分支是这样的 ：

可以看出，第一层每个数有三个分支，第二层每个数有两个分支，第三层每个数有一个分支。

也就是说，这个搜索树的分支具有收敛性。

这中枚举的功能是 其中的每个分支都是在当前未选择的数中挑选一个，具体可以看图。

时间复杂度 $O(P_n^m)$

int st[N];//存储方案
bool used[N];//标记数字是否被用过，true表示被用过，false表示没被用过
int n;

void dfs(int u) {   //当前枚举第u位
    if (u > n) {
        for (int i = 1; i <= n; i ++ ) 
            printf("%d ", st[i]);   //打印方案
        puts("");
        return ;
    }

    for (int i = 1; i <= n; i ++ ) {    //依次枚举每个数
        if (!used[i]) {                 //当前数可用
            st[u] = i;
            used[i] = true;
            dfs(u + 1);

                            //恢复现场
            st[u] = 0;      //可省略
            used[i] = false;//不可省
        }
    }
}

int main() {
    scanf("%d", &n);

    dfs(1);

    return 0;
}

$1.4$ 记忆化搜索初步

1.记忆化搜索的思想

在搜索过程中，会有很多重复计算，如果我们能记录一些状态的答案，就可以减少重复搜索量

2、记忆化搜索的适用范围

根据记忆化搜索的思想，它是 解决重复计算，而不是重复生成

也就是说，这些搜索必须是在 搜索 扩展路径的过程中分步计算的题目，也就是“搜索答案与路径相关”的题目，而不能是 搜索一个路径之后才能进行计算的题目，

必须要分步计算，并且搜索过程中，一个搜索结果必须可以建立在 同类型问题 的结果上，也就是类似于动态规划解决的那种。

也就是说，他的问题表达，不是 单纯生成一个走步方案，而是生成一个走步方案的代价等，而且每走一步，在 搜索树/图 中生成一个新状态，都可以精确计算出到此为止的费用。

也就是，可以分步计算，这样才可以 套用已经得到的答案

3、记忆化搜索的核心实现

$a.$ 首先，要通过一个表 记录已经存储下的搜索结果，一般用 哈希表 实现

$b.$ 状态表示，由于是要用 哈希表 实现，所以状态最好可以用数字表示，常用的方法是把一个状态连写成一个 $p$ 进制数字，然后把这个数字对应的十进制数字作为状态

$c.$ 在每一状态搜索的开始，高效的使用哈希表搜索这个状态是否出现过，如果已经做过，直接调用答案，回溯

$d.$ 如果没有，则按正常方法搜索

4、记忆化搜索是类似于动态规划的，不同的是，它是倒做的“递归式动态规划”。

---

第二章 DFS 题目的状态空间与转换

---

$2.1$ DFS 在地图类问题的转换

* DFS 维护连通块

在一个平面的地图上，仅用 $x、y$ 这两个坐标就可以描述地图上任意一个点。

将 起点 看作 根， 起点可走到的格子 看作往外延伸的 子节点，在搜索过程中维护当前答案。

通常在每次递归时，我们会 新建一个变量（或在全局开一个数组）来累计答案。

但经过仔细分析之后，可以得出，这类问题的 搜索答案往往与路径相关，所以，可以用记忆化搜索解决。

下一步，就是如何处理状态。

下面这个程序所解决的题目，只需要知道 第$x, y$个格子是否被遍历过，由于此题的数据是一张图，所以不需要回溯。

只需要用一个数组的值就可以精准记录了。

int dfs(int x, int y)
{
    int cnt = 1;

    st[x][y] = true;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];

        if (a < 0 || a >= h || b < 0 || b >= w) continue;

        if (g[a][b] != '.') continue;
        if (st[a][b]) continue;

        cnt +=  dfs(a, b);  // 相加
    }

    return cnt;
}

* DFS 有约束的跑图问题

往往一道 $DFS$ 的题目会给你加上各式各样的约束，如何将这些约束合适的表达出来。

就是一门值得深究的学问了。

【例题 1】 滑雪

这是一道非常经典的题目，也是作者在 3个月前，初学 $DFS$ 的时候印象极为深刻的题目之一。

面对一道陌生的问题，我们需要对它进行合理的转化（至少在联赛难度的时候这个方法是适用的）

很明显，我们可以从图上任意一点出发，搜索可以滑的最大距离，维护最大值即可。

但这样的复杂度是 $O((nm)^2)$, 显然超时。

结合 池塘计数 一题, 我们知道，并不是每一次搜索的时候都要将所有点都搜一遍。

回到此题，由于每一个点的 最大滑行距离固定，而对任意一个点而言，其最大滑行距离等价于

他能滑到的点中滑行距离最大的点 加 $1$。

所以，我们可以用 $f$ 数组记忆化维护每个点的最大滑行距离，在搜到这个点时，直接返回 $f$ 中储存的数即可。

【例题 2】 方格取数

无疑，这是一道经典模型的加强，让我们先为它划定状态空间。

即对于此图上的任意一点都有 三个变量，它的 $x, y$ 坐标和它上一步的方向 $k$。

这三类变量都可以用一个 $f$ 的三维数组来储存，设 $a, b, p$ 意义分别对应上面的 $x, y, k$。

若 $f[a][b][p]$ 被更新过，有知，$f[a][b][p]$ 储存的是 $a, b$ 坐标，上一步为 $p$ 的最大值，所以不用继续搜。

同时，我们还不能 重复经过一个格子，所以，需要用 $st$ 来判断格子是否已经经过，

需要注意的是，$st$ 并不是记忆化搜索，因为 到达一个格子的状态可能有很多个，不能以一概全。

所以我们还要在 延伸后回溯。

值得注意的是，以上操作都是在默认从终点出发为前提的，那么，其递归边界就是 起点。

状态转移，由于数据的特殊，我们将数据 逆时针转 90度 来看，那么三个转移过程是：

0. 向左转移

LL Left(int x, int y)
{
    int a, b;
    LL ans = -INF;
    a = x - 1;
    b = y;
    if (check(a, b) && !st[a][b]) 
    {
        LL res = max(dfs(a, b, 1) + g[x][y], dfs(a, b, 2) + g[x][y]);
        ans = max(ans, res);
    }
    return ans;
}

1. 向上转移

LL Up(int x, int y)
{
    int a, b;
    LL ans = -INF;
    a = x;
    b = y - 1;
    if (check(a, b) && !st[a][b]) 
    {
        LL res = max(max(dfs(a, b, 0) + g[x][y], dfs(a, b, 2) + g[x][y]), dfs(a, b, 1) + g[x][y]);
        ans = max(ans, res);
    }
    return ans;
}

2. 向右转移

LL Right(int x, int y)
{
    int a, b;
    LL ans = -INF;
    a = x + 1;
    b = y;
    if (check(a, b) && !st[a][b]) 
    {
        LL res = max(dfs(a, b, 1) + g[x][y], dfs(a, b, 0) + g[x][y]);
        ans = max(ans, res);
    }
    return ans;
}

递归代码：

inline bool check(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
inline LL dfs(int x, int y, int k)
{
    LL &ans = f[x][y][k];
    if (ans != -INF)
    {
        return ans;
    }

    st[x][y] = true;

    if (k == 0) ans = max(ans, Right(x, y));
    if (k == 1) ans = max(ans, Up(x, y));
    if (k == 2) ans = max(ans, Left(x, y));

    st[x][y] = false;
    return ans;
}

* DFS 解决棋盘类问题

我们在研究深搜算法时经常能碰到这一类问题：

在某个棋盘上有一种棋子，问最多放下几个棋子，使得剩下来的棋子两两不攻击。

这就是 棋盘类问题。

或者，也可以广义的理解为，在一张图上放上一些满足一定规律的点，让你输出其中的 放点方案 或者是 方案数。

常考题型有 八皇后问题、数独问题、多米诺骨牌（块状覆盖问题）。

下面我会教大家解决这些问题的变种，难度按递增顺序排列。

【例题 1】 棋盘问题

这是一道经典问题的变形，同样也是方案数类问题的基础题，看似简单，却往往能将你折磨得怀疑人生。

让我们从头分析吧！

首先，确定搜索方式，显然是一个排列型枚举。

但如果这样，它的时间复杂度会飙升到 $64！$, 不能接受，所以，我们需要根据题意进行简化。

通常，可以用两个数组来记录 这一行或者这一列 是否有了棋子。

或者，也可以直接 按行枚举，提升效率。

然后，就要确定搜索边界，通常有两个：越出边界 和 枚举完所有数字。

其实，还是挺简单的，那就稍微加深点难度吧！

【例题 2】 数独

非常经典的问题，也是一道用来练习码力的入门题，在做完猪国杀之前，一度是我调试代码的噩梦。

这道问题涉及的内容很多，如果你不知道怎么剪枝来提升效率，可以先学习一下我之后分享的内容。

话不多说，让我们先来看一下搜索方式，显然，每个位置都有很多种填数的方案，是 排列型枚举

在想一下有哪些需维护的信息，例如，枚举的空格数便是其中之一，注意只有没有数字的格子才能去填。

数独问题是一道典型的 $NPC$ 问题，我们需要进行回溯，通常使用二进制 $hash$表的方式来储存数独问题的状态。

边界就很显然了，在它的所有空格都正确填完之后，返回输出即可，一般是保证了唯一解的。

如果你觉得简单的话，也可以试一下这道题，无疑是对自己程序设计的一个挑战。

【习题 1】 数独2

让我们来看一道算法竞赛题真正的难度吧！

即使是身经百战的老手也很难快速解决这种问题，但也是你迈向更高道路上必经之路。

$2.2$ DFS 搜索最优解

这一类问题需要你在搜索的过程中，保留局部最优方案，排除劣于局部最优的方案，进而得出全局最优解。

下面会介绍解决这一类问题的两种方案。

1. 贪心法

将答案进行比对，保留自己需要的哪个答案，就是贪心法。

【例题 1】 小猫爬山

由于车和每辆缆车中装载的小猫状态并未固定，也就是说，我们需要用两个状态来表示。

状态转移途径有两条，一、装这个小猫到这个车，二、增加或不增加车

此状态边界无疑就是装完所有小猫的时候，但装完小猫的情况有很多，我们要取的就是用车数最小的一种。

2. 迭代法 / 二分法

适用于答案可能性较少或边界模糊的题目，可以规定边界，转化为满足性问题。

【例题 2】 木棒

这道题要求的是木棒的可能最小长度。

由于木棒的总长度固定，所以可以转换为枚举目标木棍长度（显然是整除总长度的）。

由于已拼好的木棒不用重拼，所以可以将边界设为已拼好木棒总长度 = 木棒总长度，

由于木棒的拼接是有序的，也可以说是一个 $DFS$ 的基本拼凑类题目。

由此推出木棒数量和当前所拼木棒长度可以设为变量。

这道题的剪枝就不设为本章讲解内容了。

【例题 3】 分成互质组

这道题其实并不简单。

首先，我们确定可以使用迭代法或贪心法解决。

那此时问题就变成了，如何确定一组内任意两数互质。

可以用 gcd算法简单解决。

$2.3$ DFS 搜索最优方案路径

这是一个适用性很广的算法，体现了路径追踪的思想。

当然，你必须要保留之前递归时状态转移的过程。

上面这个图是彩铅的。

其解决方式为，由答案逆推，枚举上一层可到达答案的状态，继续逆推至起点。

【例题 1】 机器分配

由于 动态规划 的 本质 是在一个 拓扑图 内找 最短路,

我们可以把每个 状态 f[i][j]看作一个 点，状态的转移 看作一条 边，把 状态的值 理解为 最短路径长。

如此，可以构建出一个 拓扑图，从 每一个点 出发到 起点 都是最短路径，更组成了一棵 最短路树。

$2.4$ DFS 搜索方案数

乍一看，这是一个很令人难受的问题QAQ，但事实并非如此，

若将 初始状态 看成 起点，答案 看成 终点，本问可以转化为，从起点可以到达终点的 路径有多少条。

在每一次 递归到答案 时统计就可以了。

【例题 1】 背包问题求方案数

本题需要注意的点如下：

首先，本题的数据偏大，所以需要运用记忆化搜索，在状态相同时直接返回。

其次，需要注意题目中的表达，物品的总体积不超过背包容量。

最后，记得用 朴素算法 求最大价值，便于给背包划分阶段，降低枚举时间复杂度。

以下是对本题要点的解决：

第一，若将背包中的状态看成一棵 最短路树，则可以在这棵树的节点上同时保存 到达这个节点的方案，

符合 记忆化搜索 的要求，可以 直接取用。

第二，不超过 即 至多，意思为 容纳了体积小于背包容量的方案，解决方法有二：

一、同时搜索 价值相等、体积偏小 的方案，最后累计。

二、将背包取前 $0$ 个物品，体积不超过 $V$ 的所有状态的 方案数 置为 $1$，从而在搜索时钻空子，变相解决。

第三，如果不用 朴素算法，就很难确定所选物品 是否使用，到那时，就只能在计算最大价值的同时用 $Dp$ 计算了。

---

第三章 DFS 题目的复杂度优化

---

$3.1$ DFS 剪枝

五种剪枝类型

1、可行性剪枝

所谓可行性剪枝，顾名思义，就是当当前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判负，直接返回。

即：不可行，就返回。

2、排除等效冗余

所谓排除等效冗余，就是当几个枝丫具有 完全相同的效果 的时候，只选择其中一个走就可以了。

即：都可以，选一个。

3、最优性剪枝

所谓最优性剪枝，是在我们用搜索方法解决最优化问题的时候的一种常用剪枝。就是当你搜到一半的时候，已经比 搜到的最优解要不优了，那么这个方案肯定是不行的，即刻停止搜索，进行回溯。

即：有比较，选最优。

4、顺序剪枝

普遍来讲，搜索的顺序是不固定的，对一个问题来讲，算法可以进入搜索树的任意的一个子节点。但假如我们要搜索一个最小值，而非要从最大值存在的那个节点开搜，就可能存在搜索到最后才出解。而我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲，有单调性存在的搜索问题可以和贪心思想结合，进行顺序剪枝。

即：有顺序，按题意。

5、记忆化

记忆化搜索其实是搜索的另外一个分支。在这里简单介绍一下记忆化的原理：

就是记录搜索的每一个状态，当 重复搜索到相同的状态 的时候直接返回。

即：搜重了，直接跳。

例题解析

【例题 1】 木棒

这出现频率才配得上 $DFS$ 中最为经典的题目之一。

可行性剪枝 ： 木棒总长度不能整除目标木棒的长度

排除等效冗余 ：

如果这些木棒已经拼出了其中的一个目标木棒，就不用再管这些木棒了。
如果用一个木棒拼目标木棒失败了，就不用考虑与其等长的木棒了。

最优性剪枝 ： 如果当前拼出的木棒长度大于目标木棒长度，不满足。

顺序剪枝 ： 从大到小枚举木棒，可以减少深层子树大小。

【例题 2】 数独2

同样是非常经典的题目，也是一道剪枝好题。

由于数独2里 横、竖、十六宫格中 1~16 都只出现一次，

排除等效冗余 ： 填可能性最小的空格。

常数优化 ： 采用二进制解决。

其难点主要是对数独二进制的表示，思路上还是很简单的。

这是一道 NPC问题， 记得在状态转换的时候备份啊。

$3.2$ DFS 记忆化搜索

记忆化搜索其实是搜索的另外一个分支。在这里简单介绍一下记忆化的原理：

就是记录搜索的每一个状态，当 重复搜索到相同的状态 的时候直接返回。

即：搜重了，直接跳。

记忆化搜索的适用性很广，可以解决几乎所有的 $DP$问题，这在 $1.4$ 中就已经做过详细介绍。

所以，让我们直接开始上手做题吧！

【例题 1】 天气预报

状态简化 ： 只维护村子的四个角落， 证明

记忆化搜索 ： 在天数、当前云位置、四个角落离上一次降雨的天数相同时，可以直接取用，证明

常数优化 ： 布尔关系可用二进制表示，证明

【例题 2】 逛公园

本题的难点是对冗余 $K$ 的处理。

面对这一类状态空间过大的问题，最好的解决方式就是将其缩小。

所以 路径长 $<= d + K$ 可以转化成 $= {d, d + 1, d + 2, …, d + K}$

现在的问题就是如何处理 $= {d + c}$ 时满足要求的路径条数了。

这里会用记忆化搜索的方式解决。

1、解决顺序与方式

这里采用的方式是 逆推求满足性，

即先确定从起点到终点所用的冗余，再根据不同的出边转换，用反向 $Dijkstra$，快速求出出边会产生的冗余，

从而计算此后节点会产生的冗余。

注意此方法有 两个边界

【1】到达终点、没有冗余
【2】当前冗余已大于起点到终点的冗余、此后无论如何都不满足（可行性剪枝）

2、记忆化搜索 在状态相等时可以使用，如结点相同、冗余相同则方案数也相同

3. 标记数组判零环

因为 $0$ 环不会增加冗余，所以同一个冗余重复搜到了同一个结点，就代表有 $0$ 环。

但需要注意的是，即使没有 $0$ 环，也可能会有两条同冗余路径交到同一结点，这种情况怎么避免呢？

注意 $DFS$ 一条道走到黑的性质，如果在同一条链上重复搜到则是零环造成，反之则不是。

所以我们要在搜完了这条链之后解除标记。

还是挺简单哒！（也就调了一上午嘛

$3.3$ DFS 启发式搜索

启发式搜索是一种可以通过当前信息推断走哪一步最有希望搜到正确答案的算法。

想要灵活运用启发式搜索，最核心的就是学会设计估价函数，即一个可以预估未来代价的函数。

* 估价函数的设计

设计估价函数的最重要的一点就是它一定要比真实情况 更优。

因为，如果它劣于真实情况，则有可能会让正确答案一直压底，从而得到一个错误的结果。

其次，估价函数的更新必须是在线的，也就是说，在搜索过程中，估价函数要随之更新。

通常都是采取 预处理 或 找规律 的方式设计估价函数。

* 估价函数的使用方式

首先要明确估价函数的作用 排除无用解 和 找到最优解。

如果可以确定 目标状态大小 就可以通过 排除无用解 来进行剪枝，这也被称为 $IDA*$

当然也可以通过一些动态处理 $max/min$ 的数据结构，如堆、线段树、平衡树，

来 优先 更新 当前值 $+$ 期望值 最优的解。

$DFS$ 常用 $IDA*$，即迭代法 $+$ 启发式解决，若搜索层数过深，也可以改用二分。

$BFS$ 等最短路算法则常用 $A*$，可以方便的进行动态更新。

但相较而言，$IDA*$ 要更好写一些。

【例题 1】排书

看到此题，我们先分析一下搜索框架。

枚举的分支是书抽出时的 首尾位置 和 插入的位置，记得在每一次搜索完后回溯，搜索新的分支。

因为搜索树的深度最多为 $5$，所以可以定义一个 $w[5][N]$ 的数组来记录原顺序（零步、一步、两步…）。

然后就是预估函数的处理了，请看下图：

1 2 [4 5] 3 | 6
=> 1 2 3 4 5 6    

此图意思是将 $4,5$ 移到 $3$ 的后面。

这一个操作更改了 $2, 3, 5$ 三数的后效数字，是移数增加答案的 最优情况，也是本题预估函数的公式。

即，错位数 $/ 3 $的上取整。

---

第四章 DFS 树与图上应用

---

$4.1$ DFS 信息传递

根据所放位置的不同，信息传递的先后会有差异。

如将 信息传递的代码 放在递归函数的 前面，就是 先更新信息，再搜索下一个阶段。

若是放在 后面 就会导致，只有将这一条链搜完之后才可以从 最底层的阶段往上 维护信息。

这就是信息传递的两种形式：由后向前 和 由前向后。

如 带权并查集 对 权值维护 的搜索顺序就是 由后向前 维护权值，再从代表元起 由前向后 更新节点。

$4.2$ DFS 信息维护

* 整体思想

【例题 1】 传染病控制

本题题意：

有一棵树，你需要在这棵树的 每一层 找到一个子树砍掉，求剩余子树的 最小值。

确实我们要维护的信息 子树的数量 后暴力枚举即可。

需要注意的是 删掉子树 的操作怎么实现，以下提供一种解决途径：

一、给子树的所有边 染色，相当于 标记数组。

注意要对这棵树 分层 以便于枚举。

【例题 2】 表达式

本题是 后缀表达式 读入，可以直接用 一个栈， 每读到符号时，就弹出变量。

由于题目中的变量都是 布尔值，容易储存管理，可以想一下是否能用一种方便的形式 打包处理。

通过 $Trie$ 树，我们可以想到用树形结构储存可以降低查找的时间，但遍历统计值又太麻烦。

不过本题的所有询问都是 无后效性的，

所以，可以考虑预处理一下 哪些值更改会影响答案，预处理完，就可以 $O(1)$ 回答了！

代码

* 特殊性质

【例题 1】 树的直径

一棵树的直径 等价于这棵树的 最长边边权。

算法步骤：

• 任选一点为 $u$
• 找到距离 $u$ 最远的节点 $v$
• 找到距离 $v$ 最远的节点 $f$
• $v$ -> $f$ 是树的一条直径

证明如下：

设 树的一条直径 为 $b$ -> $c$

则 $b$ -> $c$ 和 $u$ -> $v$ 之间有两种可能情况。

若 $b$ -> $c$ 和 $u$ -> $v$ 不相交，则分别两路径上选一点，连接为 $x$ -> $y$

因为 $u$ -> $v$ $>=$ $u$ -> $c$

所以 $v$ -> $x$ $>=$ $x$ -> $y$ $+$ $y$ -> $c$

进而 $v$ -> $x$ $+$ $x$ -> $y$ $>=$ $y$ -> $c$

则 $v$ -> $x$ $+$ $x$ -> $y$ $+$ $y$ -> $b$ $>=$ $b$ -> $c$

所以 $v$ -> $f$ $>=$ $b$ -> $c$

又因为 $b$ -> $c$ 为树的一条直径，所以 $v$ -> $f$ 也为树的一条直径。

若 $b$ -> $c$ 和 $u$ -> $v$ 相交，其交点为 $g$

则 $v$ -> $g$ $>=$ $g$ -> $c$

进而 $v$ -> $g$ + $g$ -> $b$ >= $b$ -> $c$

所以 $v$ -> $f$ $>=$ $b$ -> $c$

又因为 $b$ -> $c$ 为树的一条直径，所以 $v$ -> $f$ 也为树的一条直径。

【例题 2】 树的中心

一道练习 信息传递方向 的好题。

让我们再回顾一下信息传递的两个方向：由前往后 和 由后往前。

概括性解释的话，就是用 $DFS$ 实现的 递推 和 递归。

那这两个概念的本质如下：

递推：由已知推未知, 呈发散性
递归：逆序的递推, 呈收敛性

再让我们解析一下本题所需的两个 $DFS$ 函数。

第一个函数，求子树内的节点对当前节点的贡献。

为什么这要 由后往前 计算？

这其实并不好理解，倒不如用 反证法 想一下为什么不能 由前往后。

因为这个函数要求计算的是其 子树，若由前往后，则祖先节点值已知，其子树值未知。

这不是满足了 由已知推未知 吗？

没有，因为我们要做的是 由子树推其祖先，所以顺序出错了，正确的顺序是 由后往前

第二个函数，父亲节点对当前节点的贡献。

此时我们不需要靠子节点，就能计算出父节点的贡献，而由父节点推子节点也恰好符合 由前往后 的要求。

若这么计算，没办法计算出 祖先节点 的贡献值，就可以 事先预处理 或 建虚拟源点