《算法竞赛进阶指南》0x24 迭代加深
迭代加深
深度优先搜索每次选定一个分支，不断深入，直到到达递归边界才回溯
这种策略带有一定的缺陷：如果搜索树每个节点的分支数目非常多，且问题的答案在某个较浅的结点上，如果深搜在一开始选错了分支，就可能在不包含答案的深层次树上浪费许多时间
此时，我们可以从小到大限制搜索的深度，如果在当前深度限制下搜不到答案，就把深度限制增加，重新进行一次搜索，这就是 迭代加深 思想
所有，当搜索树规模随着层次的深入增长很快，并且我们能够确保答案在一个较浅层的结点 时，就可以采用 迭代加深的深度优先搜索算法来解决问题
双向搜索
除了 迭代加深 之外，双向搜索 也可以避免在深层子树上浪费时间
在一些题目中，问题不但具有 “初态”，还具有明确的 “终态”，并且从初态开始搜索与从终态开始逆向搜索产生的搜索树都能覆盖整个状态空间
在这种情况下，就可以采用 双向搜索：从初态和终态出发个搜索一半状态，产生两棵深度减半的搜索树，在中间交汇、组合成最终的答案
双向搜索同样避免了层数过深时分支数量的大规模增长
习题
加成序列
题目描述
满足如下条件的序列
（序列中元素被标号为
）被称为“加成序列”：
- 对于每个
都存在两个整数
和
（
，
和
可相等），使得
你的任务是：给定一个整数
，找出符合上述条件的长度
最小的“加成序列”。
如果有多个满足要求的答案，只需要找出任意一个可行解。
输入格式
输入包含多组测试用例。
每组测试用例占据一行，包含一个整数
。
当输入为单行的
时，表示输入结束。
输出格式
对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。
每个输出占一行。
数据范围
输入样例：
5
7
12
15
77
0
输出样例：
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77
解析
搜索框架：依次搜索序列中每个位置
，枚举
和
作为分支，把
填入
然后递归到下一个位置
加入剪枝：
优化搜索顺序：枚举
和
时从大到小枚举
排除等效冗余：对于不同的
可能他们的和相等，因此每层设置一个布尔数组进行判重
观察发现
的值不会太大，而每次枚举两个数字之和导致分支很多，因此考虑采用迭代加深的搜索方式
#include <iostream>
using namespace std;
const int N = 110;
int n;
int x[N];
bool dfs(int dep, int max_depth)
{
if (dep > max_depth) return x[dep - 1] == n;
bool st[N] = {0};
for (int i = dep - 1; i; i -- )
{
for (int j = dep - 1; j; j -- )
{
int s = x[i] + x[j];
if (s > n || s <= x[dep - 1] || st[s]) continue;
st[s] = true;
x[dep] = s;
if (dfs(dep + 1, max_depth)) return true;
}
}
return false;
}
int main()
{
x[1] = 1;
while (scanf("%d", &n), n)
{
int max_depth = 1;
while (!dfs(2, max_depth)) max_depth ++ ;
for (int i = 1; i <= max_depth; i ++ )
printf("%d ", x[i]);
puts("");
}
return 0;
}
送礼物
题目描述
达达帮翰翰给女生送礼物，翰翰一共准备了
个礼物，其中第
个礼物的重量是
。
达达的力气很大，他一次可以搬动重量之和不超过 W 的任意多个物品。
达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数，分别代表
和
。
以后
行，每行一个正整数表示
。
输出格式
仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。
数据范围
输入样例：
20 5
7
5
4
18
1
输出样例：
19
解析
本题为 “子集和” 问题的扩展：从给定
个数中选择几个数，使得和最接近
本题也是 "大体积" 的背包问题，状态的属性是方案是否存在，因此可以直接用
位二进制数存储这些状态做 DP
搜索做法就是进行 “指数型” 枚举，搜索每个礼物选还是不选，时间复杂度为
对于该数据范围，时间复杂度过高，考虑使用双向搜索的思想，把礼物分成两半
先对前一半做一遍深搜，把所有总和小于
的子集存放在一个数组
中，排序去重
再对后一半做一遍深搜，把所有总和小于
的子集，加上一个
数组中的数，使得加上后仍小于
且最大
这就是双向搜索的大致思路，对于后半段找
中数的操作，由于
数组有序，因此可以用二分
故时间复杂度为：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 50, M = N / 2;
int n, w, mid, g[N], a[1 << M], al;
int res;
//正向深搜，指数型枚举，记录所有的边界状态值
void dfs1(int dep, LL cur_w)
{
if (cur_w > w) return;
if (dep > mid)
{
a[ ++ al] = (int)cur_w;
return;
}
dfs1(dep + 1, cur_w + g[dep]);
dfs1(dep + 1, cur_w);
}
//逆向深搜，指数型枚举，搜到问题状态空间的边界时，二分正向搜素的最大匹配值
void dfs2(int dep, LL cur_w)
{
if (cur_w > w) return;
if (dep > n)
{
int l = 1, r = al;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (cur_w + a[mid] <= w) l = mid; else r = mid - 1;
}
res = max(res, (int)cur_w + a[r]);
return;
}
dfs2(dep + 1, cur_w + g[dep]);
dfs2(dep + 1, cur_w);
}
int main()
{
scanf("%d%d", &w, &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &g[i]);
// 优化搜索顺序
sort(g + 1, g + n + 1);
reverse(g + 1, g + n + 1);
// 切分中点，双向搜索
mid = (n + 1) >> 1;
// 正向深搜
dfs1(1, 0ll);
// 排序去重起点所在的状态空间连通块边界点的值
sort(a + 1, a + al + 1);
al = unique(a + 1, a + al + 1) - a - 1;
// 逆向深搜
dfs2(mid + 1, 0ll);
printf("%d\n", res);
return 0;
}
腾讯云开发者
