【深搜】问题模型总结
2025-10-31 20:18:31
发布于：上海
本贴仅供学习使用，请勿非法传播
upd: 2025.5.4
- 细化了部分题目描述。
0 基本概念
0.1 深搜的基本概念
深搜本质就是枚举，深搜算法的思想与枚举算法的思想类似，都需要考虑三个要素：
-
① 枚举对象（每一次递归要枚举的对象）
-
② 枚举范围（递归的终止条件）
-
③ 判定条件（一次递归到达终点时，判断搜索的方案是否合法）
所有深搜算法的实现都基于这三个步骤。
0.2 深搜的剪枝
0.2.1 优化搜索顺序
在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序索会产生不同的搜索树形态，其规模大小也相差甚远。
如：排序后优先枚举较大的数。
0.2.2 排除等效冗余
在搜索过程中，如果我们能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。
0.2.3 可行性剪枝
在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界，就执行回溯。这就好比我们在道路上行走时，远远看到前方是一个死胡同，就应该立即折返绕路，而不是走到路的尽头再返回。
如：
-
某些题目条件的范围限制是一个区间，此时可行性剪枝也被称为“上下界剪枝”。
-
求最小值时，某一次搜索已经超过了之前保存的答案。
0.2.4 最优性剪枝
在最优化问题的搜索过程中，如果当前花费的代价已经超过当前搜到的最优解，那么无论采取多么优秀的策略到达递归边界，都不可能更新答案。此时可以停止对当前分支的搜索，执行递回溯。
0.2.5 记忆化搜索（DP）
可以记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回。
如：对图进索深度优先遍历时，标记一个节点是否已经被访问过。
1 模型1：01枚举
1.1基本概念
DFS枚举的A题型，选或不选，也就是枚举每一个元素，对于每种元素根据选或不选进行两次DFS，并使用数组来表示这个元素在本次方案中是否选取。
1.2 例题
1.2.1 撤硕管理员
题目描述
有n个同学，每个同学上撤硕需要支付一定的费用，费用由一个数组a表示。小A可以选择任意数量的同学（从0个到n个）来上撤硕，但希望所选同学的支付费用之和是一个质数。计算所有满足条件的方案的总数。
思路
-
枚举对象
- 每一次递归需要枚举的对象是当前同学是否被选中。
- 对于第 i 个同学，有两种选择：
o 选中该同学，累加其费用。
o 不选中该同学，继续递归。
-
枚举范围
- 递归的终止条件是所有同学都已经被处理完毕（即递归深度达到 n+1）。
- 当递归深度达到 n+1 时，判断当前方案的总费用是否为质数。
-
判定条件
- 当递归到达终点时（即所有同学都已被处理），判断当前方案的总费用是否为质数。
- 如果是质数，则方案数加 1。
代码实现
#include<iostream>
using namespace std;
int n;
int a[20], vis[20];//a数组表示读入的数据，vis[i]表示第i个人是否上撤硕
long long int ans;
bool isprime(int x) {//判断质数函数
if (x == 1 || x == 0) return 0;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return 0;
}
return 1;
}
void check() {
int sum = 0;//统计和
for (int i = 1; i <= n; i++) {
if (vis[i]) {//如果第i个人上撤硕了
sum += a[i];//和加上这个人上撤硕的费用
}
}
if (isprime(sum)) ans++;//如果是质数，则合法
return ;//否则不合法
}
void dfs(int k) {
if (k == n + 1) {//如果已经判断到了第n+1个人，表示找到了一种方案
check();//判断这个方案是否合法，更新答案
return;
}
dfs(k + 1);
vis[k] = 1;
dfs(k + 1);
vis[k] = 0;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
dfs(1);//从第一个人开始枚举
cout << ans;
return 0;
}
2 模型2：排列型枚举问题
2.1 基本概念
枚举题中的B题型，在每一次DFS中通过for循环遍历所有可能被选取的数据，统计答案。
2.2 例题
2.2.1 食堂管理员
题目描述
小A需要为个同学分配食物，其中：
- 第个同学可以吃到份食物（）
- 要求所有同学吃的食物总数是k的倍数
- 按字典序输出所有可能的分配方案
思路
-
问题分析
我们需要为每个同学分配食物数量，使得所有同学吃的食物总数是 kk 的倍数。每个同学的食物数量可以从 1 到 aiai 中选择。我们需要按字典序输出所有满足条件的方案。 -
算法选择
由于 n≤8n≤8 且 ai≤5ai≤5，总组合数为 58=39062558=390625，完全可以通过 深度优先搜索（DFS） 枚举所有可能的组合。 -
深度优先搜索（DFS）
DFS 是一种递归算法，用于遍历所有可能的组合。在本题中，DFS 的递归树如下：- 根节点：未分配任何同学的食物数量
- 分支：每个同学的食物数量从 1 到 aiai
- 叶子节点：所有同学的食物数量都已确定
在 DFS 过程中，我们记录当前的食物分配方案，并检查总和是否是 kk 的倍数。
-
字典序输出
在 DFS 中，按从小到大的顺序枚举每个同学的食物数量，确保输出的方案是字典序的。
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
int r[10],a[10];//r数组表示第i个数字（位置）选择的值
//a数组表示输入的第i个数字的选择范围
void check(){
int sum=0;//求和
for(int i=1;i<=n;i++){
sum+=r[i];
}
if(sum%k==0){//和是k的倍数
for(int i=1;i<=n;i++){//输出方案
cout<<r[i]<<" ";
}
cout<<endl;
}
}
void dfs(int x){//枚举的是第x个数字
if(x==n+1){//找到一种方案
check();//判断是否合法
return ;
}
for(int i=1;i<=a[x];i++){
r[x]=i;//第x个数字选择的值是i
dfs(x+1);//枚举下一个数字
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
dfs(1);
return 0;
}
2.2.2 组合
n个数中选k个。
#include<bits/stdc++.h>
using namespace std;
int n, k;
int a[25];
int used[25];
int ans;
bool is_prime(int n) {
if (n <= 1) return false;
else {
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
}
return true;
}
void DFS(int m,int start) {//m代表选中的个数，start是搜索的范围
if (m == k) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (used[i] == 1) {
sum += a[i];
}
}
if (is_prime(sum)) ans++;
}
else {
for (int i = start; i < n; i++) {
if (!used[i]) {
used[i] = 1;
DFS(m + 1,i + 1);
used[i] = 0;
}
}
}
}
int main(){
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
memset(used, 0, sizeof(used));
ans = 0;
DFS(0,0);
cout << ans;
return 0;
}
2.2.3 全排列
1到n所有不重复的排列。
#include<bits/stdc++.h>
using namespace std;
const int N = 2001;
int n, a[N], vis[N];
void dfs(int x)
{
if(x == n + 1)
{
for(int i = 1; i <= n; ++i)
cout << setw(5) << a[i];
cout << endl;
}
for(int i = 1; i <= n; ++i)
{
if(!vis[i])
{
vis[i] = 1;
a[x] = i;
dfs(x + 1);
vis[i] = 0;
}
}
}
int main(){
cin >> n;
dfs(1);
return 0;
}
2.2.4 特殊全排列
从某一特定排列开始继续全排列且经过m次停止。
void DFS(int all) {
if (flag == 1) return;
if (all == n + 1) {
cnt++;
if (cnt == m + 1) {
for (int i = 1; i <= n; i++) {
cout << a[i];
if (i != n) cout << " ";
}
flag = 1;
}
}
else {
for (int i = 1; i <= n; i++) {
if (cnt == 0) i = a[all]; //关键就是这一句
if (!used[i]) {
used[i] = 1;
a[all] = i;
DFS(all + 1);
used[i] = 0;
}
}
}
}
3 模型3：连通性模型
3.1 基本概念
连通性模型即连通块问题，通常使用dfs或bfs搜索连通块的个数。
3.2 迷宫类型的连通块
3.2.1 数水坑
题目描述
题目描述的是由于降雨，农民约翰的田地被表示为一个N×M的网格图，每个格子要么是水（'W'），要么是旱地（'.'）。一个水坑的定义是由相连的'W'组成的区域，其中“相连”指的是一个格子与其周围的八个格子（即上下左右及四个对角线方向）相邻。求给定的网格中有多少个独立的水坑。
思路
-
输入网格：
- 读取网格的行数 NN 和列数 MM
- 读取网格的内容，存储为一个二维字符数组
-
遍历网格：
- 对于每个网格，如果它是 "W" 且未被访问过，则启动 DFS 或 BFS，将其周围所有相连的 "W" 标记为已访问
- 每启动一次 DFS 或 BFS，水坑的数量加 1
-
输出结果：
- 输出水坑的总数
代码实现
3.3 图上的连通块
3.3.2 无向图的遍历
题目描述
给出一个用邻接矩阵存储的无向图，输出它的深度优先遍历序列。
【搜索】【深度优先】无向图的遍历_信奥算法普及-_官方-ACGO题库
思路
- 输入处理：首先读取图的顶点数 nn，然后读取 n×nn×n 的邻接矩阵。
- DFS实现：从顶点1开始，使用递归或栈来实现DFS。在遍历时，标记已访问的顶点，避免重复访问。
- 输出结果：按照DFS遍历的顺序输出顶点编号，并用
-连接。
代码实现
#include<iostream>
using namespace std;
int n,mp[25][25],path[25];
bool vis[25];
int idx;
void dfs(int x){
for(int i =1;i<=n;i++){
if(!vis[i] && mp[x][i]){
path[++idx] = i;
vis[i]=1;
dfs(i);
}
}
}
int main(){
cin >> n;
for(int i =1;i<=n;i++){
for(int j =1;j<=n;j++){
cin >> mp[i][j];
}
}
vis[1]=1;
dfs(1);
cout << 1;
for(int i=1;i<n;i++){
cout << '-' << path[i];
}
return 0;
}
4 模型4：迭代加深
4.1 基本概念
迭代加深是一种每次限制搜索深度的深度优先搜索。这种搜索算法通常用于具有较大搜索空间的问题，其中搜索树的分支非常多，而问题的答案在某个较浅的节点上。为尽量减少在无用分支上浪费的时间，可以使用迭代加深搜索。
它的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度d ，当d达到设定的深度时就返回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度+1 ，重新从根开始。
既然是为了找最优解，为什么不用BFS呢？我们知道BFS的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的BFS就显出了劣势。事实上，迭代加深就类似于用DFS方式实现的BFS，它的空间复杂度相对较小。
当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成BFS的。
4.2 例题
4.2.1 加成序列
题目描述
序列 称为加成序列当且仅当满足：
- 首项固定：
- 末项指定：
- 严格单调性：
- 加成性质： 使
思路
首先设定一个较小的深度作为全局变量，进行DFS。每进入一次DFS，将当前深度d++ ，当发现d大于设定的深度就返回。如果在搜索的途中发现了答案就可以回溯，同时在回溯的过程中可以记录路径。如果没有发现答案，就返回到函数入口，增加设定深度，继续搜索。
代码实现
//AcWing 170. 加成序列
//迭代加深
//优化搜索顺序
//排除等效冗余
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 105;
int n;
int path[N];
bool dfs(int u, int depth) {
if (u > depth) return false;
if (path[u - 1] == n) return true;
bool st[N] = { 0 };//当前分支不选用重复的数字，不是状态的一部分
//枚举第u层之前的数字
for (int i = u - 1; i >= 1; i--) {//优化搜索顺序
for (int j = i; j >= 1; j--) {
int s = path[i] + path[j];
//排除等效冗余
if (st[s] || s > n || s <= path[u - 1]) continue;
st[s] = true;
path[u] = s;//不显示的恢复现场
if (dfs(u + 1, depth)) return true;
}
}
return false;
}
int main(){
path[1] = 1;
while (cin >> n, n) {
int depth = 2;
while (!dfs(2, depth)) depth++;
for (int i = 1; i < depth; i++) cout << path[i] << " ";
cout << endl;
}
return 0;
}
5 模型5：双向深搜
5.1 基本概念
除了迭代加深之外，双向搜索也可以避免在深层子树上浪费时间。在一些题目中，问题不但具有“初态”，还具有明确的“终态”，并且从初态开始搜索与从终态开始逆向搜索产生的搜索树都能覆盖整个状态空间。在这种情况下，就可以采用双向搜索--从初态和终态出发各搜索一半状态，产生两棵深度减半的搜索树，在中间交会、组合成最终的答案。
如下图所示，图1是直接进行一次搜索产生的搜索树，图2是双向搜索的两棵搜索树，避免了层数过深时分支数量大规模增长。
S（起点）
/ | \
A B C
/ | \ ...
D E F
/ | \ ...
G H I
...（继续加深）
S
/ \
A B
/ \ \
C D E
/ / \ \
F G H I
| |
J K
\ /
M（相遇点，同时属于正向和反向路径）
|
N
/ \
O P
/ \
Q R
/ \
T（终点，反向搜索的起点）
5.2 例题
5.2.1 送礼物
题目描述
翰翰准备了 N 个礼物，第 i 个礼物的重量是 G[i]。达达的力气可以搬动总重量不超过 W 的任意多个物品。我们需要找到在这些物品中，达达一次性能搬动的最大总重量，即不超过 W 的最大子集和。
思路
这道题目是"子集和"问题的拓展——从给定的 N 个数中选择几个，使它们的和最接近 W。这类问题本质上是一个"大体积"的背包问题。
直接解法是进行指数型枚举——搜索每个礼物选还是不选，时间复杂度为 O(2N)O(2N)。可以通过剪枝优化：当已选礼物重量之和大于 W 时及时剪枝。
由于 N≤45N≤45，245245 的复杂度过高，因此采用双向搜索的思想：
- 划分礼物：将礼物分成两半
- 第一次搜索：从前一半礼物中选出所有可能的重量值（0~W之间），存入数组 A 并排序、去重
- 第二次搜索：从后一半礼物中选出一些，对于每个可能的重量值 t，在数组 A 中二分查找 ≤ W−tW−t 的最大值，用二者的和更新答案
时间复杂度优化：从 O(2N)O(2N) 降为 O(N⋅2N/2)O(N⋅2N/2)
进一步优化：
- 优化搜索顺序：将礼物按重量降序排序后再分半搜索
- 调整划分点：增加第一次搜索的礼物数，减少第二次搜索的礼物数。实验表明取前 N2+12N+1 个礼物为"前一半"，剩余为"后一半"时效率最高
代码实现
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1 << 25; // k最大是25， 因此最多可能有2^25种方案
int n, m, k;
int g[50]; // 存储所有物品的重量
int weights[N]; // weights存储能凑出来的所有的重量
int cnt = 0;
int ans; // 用ans来记录一个全局最大值
// u表示当前枚举到哪个数了， s表示当前的和
void dfs(int u, int s)
{
// 如果我们当前已经枚举完第k个数（下标从0开始的）了， 就把当前的s， 加到weights中去
if (u == k) {
weights[cnt++] = s;
return;
}
// 枚举当前不选这个物品
dfs(u + 1, s);
// 选这个物品, 做一个可行性剪枝
if ((LL)s + g[u] <= m) { //计算和的时候转成long long防止溢出
dfs(u + 1, s + g[u]);
}
}
void dfs2(int u, int s)
{
if (u == n) { // 如果已经找完了n个节点， 那么需要二分一下
int l = 0, r = cnt - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (weights[mid] <= m - s)
l = mid;
else
r = mid - 1;
}
ans = max(ans, weights[l] + s);
return;
}
// 不选择当前这个物品
dfs2(u + 1, s);
// 选择当前这个物品
if ((LL)s + g[u] <= m)
dfs2(u + 1, s + g[u]);
}
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i++)
cin >> g[i];
// 优化搜索顺序（从大到小）
sort(g, g + n);
reverse(g, g + n);
// 把前k个物品的重量打一个表
k = n >> 1;
dfs(0, 0);
// 做完之后， 把weights数组从小到大排序
sort(weights, weights + cnt);
// 判重
int t = 1;
for (int i = 1; i < cnt; i++)
if (weights[i] != weights[i - 1])
weights[t++] = weights[i];
cnt = t;
// 从k开始， 当前的和是0
dfs2(k, 0);
cout << ans << endl;
return 0;
}
6 模型6：迭代加深启发式搜索（IDA*）
6.1 基本概念
设计一个估价函数，估算从每个状态到目标状态需要的步数。当然，与A*算法一样，估价函数需要遵守“估计值不大于未来实际步数”的准则。然后，以迭代加深DFS 的搜索框架为基础，把原来简单的深度限制加强为：若当前深度+未来估计步数>深度限制，则立即从当前分支回溯。
这就是 IDA*算法（迭代加深的 A*算法）。IDA*算法在许多场景下表现出了优秀的效率，并且程序实现的难度低于A*算法。
6.2 例题
6.2.1 排书
题目描述
给定本编号为的书，初始状态为任意排列。每次操作可以选择一段连续的书，并将其插入到任意位置。要求通过最少操作次数使书本按顺序排列。
思路
(IDA*) 时间复杂度
步骤分析：
- 每次操作：抽取长度为 ii 的一段时，有 n−i+1n−i+1 种抽取位置，对于每种抽法有 n−in−i 种插入位置
- 由于向前移动等价于向后移动（对称性），实际分支数为：
算法选择：
- 四步内解决最多有
5604个状态，会超时 - 使用 IDA* 进行优化
估价函数设计：
- 要求：估价函数值不大于实际步数
- 最终状态：每本书后面的书编号应该比当前书多 1
- 观察：每次移动最多断开 3 个相连位置，再重新加入 3 个相连位置，因此最多修正 3 个错误连接
- 设计：设当前有
tot个错误连接，则估价函数
剪枝策略：
- 当前层数 +
f(s)> 迭代加深层数上限时，直接回溯
时间复杂度：
- 理论最多
5604个状态 - 使用 IDA* 后实际搜索状态数大幅减少
参考文献：本题解参考《算法竞赛进阶指南》0x28 IDA* 一节
代码实现
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int n;
int q[N], w[5][N];
int f()
{
int res = 0;
for (int i = 0; i + 1 < n; i ++ )
if (q[i + 1] != q[i] + 1)
res ++ ;
return (res + 2) / 3;
}
bool check()
{
for (int i = 0; i < n; i ++ )
if (q[i] != i + 1)
return false;
return true;
}
bool dfs(int depth, int max_depth)
{
if (depth + f() > max_depth) return false;
if (check()) return true;
for (int l = 0; l < n; l ++ )
for (int r = l; r < n; r ++ )
for (int k = r + 1; k < n; k ++ )
{
memcpy(w[depth], q, sizeof q);
int x, y;
for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[depth][x];
for (x = l; x <= r; x ++, y ++ ) q[y] = w[depth][x];
if (dfs(depth + 1, max_depth)) return true;
memcpy(q, w[depth], sizeof q);
}
return false;
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
int depth = 0;
while (depth < 5 && !dfs(0, depth)) depth ++ ;
if (depth >= 5) puts("5 or more");
else printf("%d\n", depth);
}
return 0;
}
6.2.2 回转游戏
题目描述
给定一个#形棋盘，包含24个格子，其中数字1、2、3各出现8次。定义8种操作（A-H），每种操作将指定方向的7个数字循环移动1位。目标是通过最少操作使中央8个格子的数字相同。
思路
(IDA*, DFS) O(r<sup>k</sup>)
本题采用 IDA* 算法，即迭代加深的 A* 算法。
估价函数设计：
- 统计中间 8 个方格中出现次数最多的数的出现次数，记为 k
- 每次操作会从中间 8 个方格中移出一个数，再移入一个数，因此最多减少一个不同的数
- 估价函数设为 8−k
剪枝策略：
- 记录上一次的操作，本次操作避免枚举上一次的逆操作
保证字典序最小：
- 由于最短操作步数一定，每一步枚举时先枚举字典序小的操作即可
时间复杂度：
- 假设答案最少需要 k 步，每次需要枚举 7 种不同操作（除了上一步的逆操作）
- 最坏情况下需要枚举 r<sup>k</sup> 种方案，但加入启发函数后实际枚举状态数很少
代码实现
/*
0 1
2 3
4 5 6 7 8 9 10
11 12
13 14 15 16 17 18 19
20 21
22 23
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 24;
int q[N];
int op[8][7] = {
{0, 2, 6, 11, 15, 20, 22},
{1, 3, 8, 12, 17, 21, 23},
{10, 9, 8, 7, 6, 5, 4},
{19, 18, 17, 16, 15, 14, 13},
{23, 21, 17, 12, 8, 3, 1},
{22, 20, 15, 11, 6, 2, 0},
{13, 14, 15, 16, 17, 18, 19},
{4, 5, 6, 7, 8, 9, 10}
};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
int opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int path[100];
int f()
{
static int sum[4];
memset(sum, 0, sizeof sum);
for (int i = 0; i < 8; i ++ ) sum[q[center[i]]] ++ ;
int s = 0;
for (int i = 1; i <= 3; i ++ ) s = max(s, sum[i]);
return 8 - s;
}
bool check()
{
for (int i = 1; i < 8; i ++ )
if (q[center[i]] != q[center[0]])
return false;
return true;
}
void operation(int x)
{
int t = q[op[x][0]];
for (int i = 0; i < 6; i ++ ) q[op[x][i]] = q[op[x][i + 1]];
q[op[x][6]] = t;
}
bool dfs(int depth, int max_depth, int last)
{
if (depth + f() > max_depth) return false;
if (check()) return true;
for (int i = 0; i < 8; i ++ )
{
if (opposite[i] == last) continue;
operation(i);
path[depth] = i;
if (dfs(depth + 1, max_depth, i)) return true;
operation(opposite[i]);
}
return false;
}
int main()
{
while (scanf("%d", &q[0]), q[0])
{
for (int i = 1; i < N; i ++ ) scanf("%d", &q[i]);
int depth = 0;
while (!dfs(0, depth, -1))
{
depth ++ ;
}
if (!depth) printf("No moves needed");
for (int i = 0; i < depth; i ++ ) printf("%c", 'A' + path[i]);
printf("\n%d\n", q[6]);
}
return 0;
}
有帮助，赞一个