深度优先搜索 学习笔记
引入
深度优先搜索 DFS 是图论中最基础，最重要的算法之一。DFS 是一种盲目搜寻法，也就是在每个点 \(u\) 上，任选一条边 DFS，直到回溯到 \(u\) 时才选择别的边，如下图。
他的搜索顺序为 1-2-3-4-6。
递归实现指数型枚举
从 \(1\sim n\) 中这 \(n\) 个整数选取任意多个，输出所有可能的选择方案。
每一个数都有选与不选两种可能，相当于在每次递归上尝试选与不选两种分支，最后的时间复杂度即为 \(O(2^n)\)。
递归实现组合型枚举
组合型枚举的实现与指数型枚举的实现十分相近，只不过该问题是必须要在 \(n\) 个数中选取 \(m\) 个数，每个数还是有选、不选两条分支，所以实现直接在“指数型枚举”中加入两个剪枝即可：
- 若当前选择的数的个数大于 \(m\) 直接返回。
若当前选择的数的个数加上剩余的数的个数小于 \(m\) 则直接返回。
时间复杂度 \(O(2^n)\)。
递归实现排列型枚举
题目链接：题目详情 - 全排列问题 - ClorOJ (zshfoj.com)。
把每个可用的数作为数列中的下一个数，求解把剩余的 \(n-1\) 个数按照任意次序排列这个规模更小的子问题。
时间复杂度 \(O(n!)\)。
例题1 拔河比赛
题目链接：题目详情 - 拔河比赛 - ClorOJ (zshfoj.com)。
首先，由 (1) 可得，若 \(n\) 为奇数，则两边的人数仅相差 \(1\)，否则若 \(n\) 为偶数，则两边人数相等。
考虑到条件 (1)，显然我们可以只构造一个长度为 \(\left\lfloor\dfrac{n}{2}\right\rfloor\) 的组。
再考虑到条件 (2)，显然两个组的体重之和 \(S\) 是固定的，肯定为 \(\sum\limits_{i=1}^{n}w_i\)。于是我们需要让这个长度为 \(\left\lfloor\dfrac{n}{2}\right\rfloor\) 的组的和尽量接近 \(\dfrac{s}{2}\)。
于是我们可以遍历每一个人，每个人要么选要么不选，即“指数型枚举”，在所有方法中找出最小的差值，即为答案。用一个三元组 \((x,y,z)\) 来描述状态，表示当前考虑到第 \(x\) 位成员，已经选择了 \(y\) 个人，体重和为 \(z\)。
代码：
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int t,n,a[100100],b[100100],s=999999999,p;
inline int min(int x,int y){return x>y?y:x;}
inline void dfs(int k,int x,int u)
{
if(x>(n-x+1)) return;
if(abs(x-n+x)<2) s=min(s,abs(k));
for(int i=u+1;i<=n;i++)
{
if(b[i]<1)
{
b[i]=1;
dfs(k-2*a[i],x+1,i);
b[i]=0;
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
p+=a[i];
}
dfs(p,0,0);
printf("%d\n",s);
for(int i=1;i<=n;i++) b[i]=0;
p=0;
s=999999999;
}
return 0;
}
剪枝
每次搜索可以看做从树根出发，遍历整棵树的过程。而所谓剪枝，即为通过某种判断，将不必要的遍历过程剪去。
使用剪枝优化的核心问题是设计剪枝的判断方法，即确定哪些枝条应该舍去，哪些枝条应该保留。设计出好的剪枝判断方法往往能使得程序运行时间大幅度缩短，否则，也可能适得其反，因为判断也需要时间。
剪枝的原则
正确性
顾名思义，剪枝需要保证正确性，否则可能会遗漏掉更优的枝条。如果剪去了正确的答案，那么剩下的操作都毫无意义。所以正确性是剪枝的前提。
准确性
尽可能剪去多的不能通向正解的枝条。剪枝方法只有在具有了较高准确性的时候，才能真正的优化时间。
高效性
当设计好剪枝后，我们可能需要对搜索树的每个枝条都进行一次判断。然而，我们一般的剪枝是基于正解的“必要条件”进行判断，所以必然有很多非正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序效率的提高无疑是具有副作用的。所以如何平衡剪枝算法的准确性与高效性，往往是搜索算法优化的关键。
剪枝的技巧
优化搜索顺序
搜索数的各个层次，各个分支之间的顺序不是固定的，不同的搜索顺序会产生不同的搜索树。
排除等效冗余
如果沿着几条不同的分支能达到的子树是等效的，那么我们只需要对其中的一条分支进行搜索即可。
可行性剪枝
对当前状态进行检查，发现若分支无法到达正确答案的递归边界，则执行回溯。好比你在路上走，远远看到前方是死胡同，则直接折返绕路。在某些题目中也称“上下界剪枝”。
最优性剪枝
在最优化问题中，若当前花费的代价已经高于之前搜到的最优解，则直接返回，因为无法比之前搜到的最优解更优了。
记忆化
记录每个状态的搜索结果，在重复遍历一个状态时直接返回之前搜过的答案。此方法应用在 DFS 搜索为图的时候，如斐波那契数列。
例题2 数独游戏
Description
把 \(9\times 9\) 的数独补充完整，使得图中每行、每列、每个 \(3\times 3\) 的九宫格内数字 \(1\sim9\) 均恰好出现一次。
考虑 DFS。
Solution 1
找出一个还没有填的位置，检查 所有合法的数字。
搜索边界：1. 填满 \(9\times 9\) 的数独；2. 发现一个位置没有能填的合法数字。
可是这样的时间复杂度还是很大。
Solution 2
考虑优化搜索顺序，我们应该优先考虑“能填的合法数字”最少的位置。考虑这个位置上填什么数字。
此外，在每个状态上记录，检索，更新的开销。用位运算代替对数独各个位置所填的数字的记录，以及可填性的检查与统计。
对于每行、每列、每个九宫格，分别用一个 9 位二进制数保存哪些数字可以填。
若一行为 101100010，即 \(1,3,4,5,8\) 为不可以填写的，而 \(2,6,7,9\) 是可以填写的。
这里的位运算是可以自行选择的。
可以做或运算，来判断某个数是否可以用。
当填写后，我们需要把九宫格更新。
Code
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int a[100][100], b[100][2], c[100], fx[10][10], fy[10][10], fg[10][10], n;
string s;
bool check(int x, int y, int t) //判断是否可填该数
{
if (fx[x][t] || fy[y][t] || fg[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][t])
return false;
else //无重复，即可填，判重数组标记为一
{
fx[x][t] = 1;
fy[y][t] = 1;
fg[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][t] = 1;
return true;
}
}
void back(int x, int y, int t) //回溯，还原信息
{
fx[x][t] = 0;
fy[y][t] = 0;
fg[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][t] = 0;
}
bool dfs(int dep) {
if (dep > n) {
n = 0;
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
if (a[i][j])
cout << a[i][j];
else
cout << c[++n];
}
}
cout << endl;
return true; //返回真，以便快速退出
} else {
int x = b[dep][0], y = b[dep][1];
for (int i = 1; i <= 9; i++) {
if (check(x, y, i)) {
c[dep] = i; //另存空格填的数
if (dfs(dep + 1))
return true; //直接退出
back(x, y, i);
}
}
}
return false;
}
int main() {
getline(cin, s);
while (s != "end") {
for (int i = 0; i < 81; i++) {
int xt = i / 9, yt = i % 9;
if (s[i] == '.') {
a[xt + 1][yt + 1] = 0;
b[++n][0] = xt + 1, b[n][1] = yt + 1; //存下空格坐标
} else {
a[xt + 1][yt + 1] = s[i] - 48;
fx[xt + 1][s[i] - 48] = 1;
fy[yt + 1][s[i] - 48] = 1;
fg[(xt / 3 * 3 + yt / 3 + 1)][s[i] - 48] = 1;
}
}
dfs(1);
n = 0;
memset(fx, 0, sizeof(fx));
memset(fy, 0, sizeof(fy));
memset(fg, 0, sizeof(fg));
getline(cin, s);
}
}
例题3 虫食算
Description
\(1\le n\le 26\).
Solution
考虑 DFS。很明显可以依次枚举每个字母代表什么数字，但 \(O(n!)\) 的复杂度很明显无法通过本题 \(n\le26\) 的数据。
如何剪枝？做加法竖式的时候要从右到左计算，考虑如何判断当前方案不合法。
从后往前枚举每一列，记当前的被加数、加数与和分别为 \(a,b,c\)，进位为 \(t\)，若出现 \(a+b+t\ne c\) 的情况则不合法。
若右边存在某个数尚未确定，那么上一位的 \(t\) 可能为 \(0,1\) 中的任意一个。这是若 \(a+b\ne c\) 且 \(a+b+1\ne c\)，那么也是不合法。
对于最高位判断是否有进位，若有进位则根据题意，和也是一个 \(n\) 位数，不合法。
Code
#include <bits/stdc++.h>
#define N 55
using namespace std;
int n, ct;
int a[N], b[N];
char s[4][N];
void dfs(int x, int y, int t) {
if (ct == 1)
return;
if (y == -1) {
if (t == 0) {
for (int i = 0; i < n; ++i) printf("%d ", a[i]);
ct = 1;
}
return;
}
for (int i = y; i >= 0; --i) {
int a1 = a[s[1][i] - 'A'], a2 = a[s[2][i] - 'A'], a3 = a[s[3][i] - 'A'];
if (a1 == -1 || a2 == -1 || a3 == -1)
continue;
if ((a1 + a2) % n != a3 && (a1 + a2 + 1) % n != a3)
return;
}
if (a[s[x][y] - 'A'] < 0) {
for (int i = n - 1; i >= 0; --i) {
if (b[i] == 0) {
if (x != 3) {
a[s[x][y] - 'A'] = i;
b[i] = 1;
dfs(x + 1, y, t);
a[s[x][y] - 'A'] = -1;
b[i] = 0;
} else {
int sum = a[s[1][y] - 'A'] + a[s[2][y] - 'A'] + t;
if (sum % n != i)
continue;
b[i] = 1;
a[s[x][y] - 'A'] = i;
dfs(1, y - 1, sum / n);
b[i] = 0;
a[s[x][y] - 'A'] = -1;
}
}
}
return;
}
if (x != 3) {
dfs(x + 1, y, t);
} else {
int sum = a[s[1][y] - 'A'] + a[s[2][y] - 'A'] + t;
if (sum % n != a[s[3][y] - 'A'])
return;
dfs(1, y - 1, sum / n);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= 3; ++i) scanf("%s", s[i]);
memset(a, -1, sizeof(a));
dfs(1, n - 1, 0);
return 0;
}
总结
深搜其实还是非常好用的。
骗分。
其实深搜的功能远远不止骗分，请举一反三。
