参考《算法竞赛进阶指南》、AcWing题库

迭代加深

迭代加深是一种 每次限制搜索深度的 深度优先搜索。

它的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度 ，当达到设定的深度时就返回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度加一，重新从根开始。

既然是为了找最优解，为什么不用 BFS 呢？我们知道 BFS 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的 BFS 就显出了劣势。事实上，迭代加深就类似于用 DFS 方式实现的 BFS，它的空间复杂度相对较小。

当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 BFS 的。

深度优先搜索每次选定一个分支，不断深入，直至到达递归边界才回溯。这种策略带有一定的缺陷。试想以下情况：搜索树每个节点的分支数目非常多，并且问题的答案在某个较浅的节点上。如果深搜在一开始选错了分支，就很可能在不包含答案的深层子树上浪费许多时间。

如果下图左半部分是问题的状态空间，五角星标识着答案，那么深度优先搜索算法产生的搜索树就如下图右半部分所示，算法在矩形圈出的深层子树上浪费了很多时间。

image-20211108010548507

此时，我们可以从小到大限制搜索的深度，如果在当前深度限制下搜不到答案，就把深度限制增加， 重新进行一次搜索，这就是迭代加深思想。所谓“迭代”，就是以上一次的结果为基础，重复执行以逼近答案的意思。迭代加深DFS 的过程如下：

image-20211108010652987

虽然该过程在深度限制为 dd 时，会重复搜索第 1∼d−11 \sim d-1层的节点，但是当搜索树节点分支数目较多时，随着层数的深入，每层节点数会呈指数级增长，这点重复搜索与深层子树的规模相比，实在是小巫见大巫了。

总而言之，当搜索树规模随着层次的深入增长很快，并且我们能够确保答案在一个较浅层的节点时，就可以采用迭代加深的深度优先搜索算法来解决问题。读者可以进行大致的估算，有些题目描述甚至会包含 “如果10 步以内搜不到结果就算无解” 的字样。

步骤

首先设定一个较小的深度作为全局变量，进行 DFS。每进入一次 DFS，将当前深度加一，当发现 大于设定的深度就返回。如果在搜索的途中发现了答案就可以回溯，同时在回溯的过程中可以记录路径。如果没有发现答案，就返回到函数入口，增加设定深度，继续搜索。

代码框架

1
2
3
4
5
6
7
IDDFS(u,d)
    if d>limit
        return
    else
        for each edge (u,v)
            IDDFS(v,d+1)
  return

注意事项

在大多数的题目中，广度优先搜索还是比较方便的，而且容易判重。当发现广度优先搜索在空间上不够优秀，而且要找最优解的问题时，就应该考虑迭代加深。

例题

加成序列

满足如下条件的序列 XX（序列中元素被标号为 1、2、3…m1、2、3…m）被称为“加成序列”：

  1. X[1]=1X[1]=1
  2. X[m]=nX[m]=n
  3. X[1]<X[2]<…<X[m−1]<X[m]X[1]<X[2]<…<X[m-1]<X[m]
  4. 对于每个 kk（2≤k≤m2 \le k \le m）都存在两个整数 ii 和 jj （1≤i,j≤k−11 \le i,j \le k-1，ii 和 jj 可相等），使得 X[k]=X[i]+X[j]X[k]=X[i]+X[j]。

你的任务是：给定一个整数 nn，找出符合上述条件的长度 mm 最小的“加成序列”。

如果有多个满足要求的答案，只需要找出任意一个可行解。

输入格式

输入包含多组测试用例。

每组测试用例占据一行，包含一个整数 nn。

当输入为单行的 00 时，表示输入结束。

输出格式

对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。

每个输出占一行。

数据范围

1≤n≤1001 \le n \le 100

输入样例：

1
2
3
4
5
6
5
7
12
15
77
0

输出样例：

1
2
3
4
5
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

算法分析

搜索框架：依次搜索序列中的每个位置kk，枚举ii和jj作为分支，把$X[i] 和和X[j]的和填到的和填到X[k]$上，然后递归填写下一个位置。

加入以下剪枝：

  • 优化搜索顺序
    为了让序列中的数尽快逼近nn, 在枚举 ii 和 jj 时从大到小枚举。

  • 排除等效冗余
    对于不同的ii和jj, X[i]+X[j]X[i] + X[j] 可能是相等的。我们可以在枚举时用一个boolbool数组对X[i]+X[j]X[i] + X[j]进行判重，避免重复搜索某一个和。
    经过观察分析可以发现， mm 的值（序列长度）不会太大（ ≤10 ) ，而每次枚举两个数的和，分支很多。所以我们采用迭代加深的搜索方式，从1开始限制搜索深度，若搜索失败就增加深度限制重新搜索，直到找到一组解时即可输出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstring>
#include <iostream>
using namespace std;
const int N = 106;
int n, ans[N], dep;

bool dfs(int now) {
	if (now == dep) return ans[now] == n;
	bool v[N];
	memset(v, 0, sizeof(v));
	for (int i = now; i; i--)
		for (int j = i; j; j--) {
			int num = ans[i] + ans[j];
			if (num <= n && num > ans[now] && !v[num]) {
				ans[now+1] = num;
				if (dfs(now + 1)) return 1;
				else v[num] = 1;
			}
		}
	return 0;
}

int main() {
	ans[1] = 1;
	while (cin >> n && n) {
		dep = 1;
		while (!dfs(1)) ++dep;
		for (int i = 1; i <= dep; i++) cout << ans[i] << " ";
		cout << endl;
	}
	return 0;
}

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;

int n, ans[N];
bool used[N];

bool dfs(int now, int depth) {
  if (now == depth) return ans[now] == n;
  memset(used, 0, sizeof used);
  for (int i = now; i; --i) {
    for (int j = i; j; --j) {
      int sum = ans[i] + ans[j];
      if (sum > n || sum <= ans[now] || used[sum]) continue;
      ans[now + 1] = sum;
      if (dfs(now + 1, depth)) return true;
      used[sum] = true;
    }
  }
  return false;
}

int main() {
  ans[1] = 1;
  while (cin >> n, n) {
    int depth = 1;
    while (!dfs(1, depth)) ++depth;
    
    for (int i = 1; i <= depth; ++i) cout << ans[i] << " ";
    cout << endl;
  }
}

双向搜索

除了迭代加深之外, 双向搜索也可以避免在深层子树上浪费时间。在一些题目中, 问题不但具有 “初态”, 还具有明确的 “终态”, 并且从初态开始搜索与从终态开始逆向搜索产生的搜索树都能覆盖整个状态空间。在这种情况下, 就可以采用双向搜索从初态和终态出发各搜索一半状态, 产生两棵深度减半的搜索树, 在中间交会、组合成 最终的答案。

如下图所示, 左侧是直接进行一次搜索产生的搜索树, 右侧是双向搜索的两棵搜索 树, 避免了层数过深时分支数量的大规模增长。

例题

171. 送礼物

达达帮翰翰给女生送礼物，翰翰一共准备了 NN 个礼物，其中第 ii 个礼物的重量是 G[i]G[i]。

达达的力气很大，他一次可以搬动重量之和不超过 WW 的任意多个物品。

达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式

第一行两个整数，分别代表 WW 和 NN。

以后 NN 行，每行一个正整数表示 G[i]G[i]。

输出格式

仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围

1≤N≤461 \le N \le 46,
1≤W,G[i]≤231−11 \le W,G[i] \le 2^{31}-1

输入样例：

1
2
3
4
5
6
20 5
7
5
4
18
1

输出样例：

1
19

算法分析

这道题目就是 “子集和” 问题的扩展一一从给定的 NN 个数中选择几个, 使它们的和最接近 WW 。了解 “背包” 问题的读者可能已经发现, 这道题目也是一个 “大体积”的背包问题。这类问题的直接解法就是进行 “指数型” 的枚举一一搜索每个礼物选还是不选, 时间复杂度为 0(2N)0\left(2^{N}\right) 。当然, 若搜索过程中已选的礼物重量之和已经大于 WW,可以及时剪枝。

此题 N≤45,245N \leq 45,2^{45} 的复杂度过高。这时我们就可以利用双向搜索的思想, 把礼物分成两半。

首先, 我们搜索出从前一半礼物中选出若干个, 可能达到的 0∼W0 \sim W 之间的所有重量值, 存放在一个数组 AA 中, 并对数组 AA 进行排序、去重。

然后, 我们进行第二次搜索, 尝试从后一半礼物中选出一些。对于每个可能达到的重量值 tt, 在第一部分得到的数组 AA 中二分查找 ≤W−t\leq W-t 的数值中最大的一个, 用二者的和更新答案。

这个算法的时间复杂度就只有 0(2N/2log⁡2N/2)=0(N∗2N/2)了0\left(2^{N / 2} \log 2^{N / 2}\right)=0\left(N * 2^{N / 2}\right) 了 。我们还可以加入一些优化, 进一步提高算法的效率:

  1. 优化搜索顺序
    把礼物按照重量降序排序后再分半、搜索。
  2. 选取适当的 “折半划分点”
    因为第二次搜索需要在第一次搜索得到的数组中进行二分查找, 效率相对较低, 所以我们应该稍微增加第一次捜索的礼物数, 减少第二次搜索的礼物数。经过本地随机数据的实验, 我们发现取第 1∼N/2+21 \sim N /2 +2 个礼物为 “前一半”, 取第 N/2+3∼NN / 2+3 \sim N 个礼物为 “后一半”时, 搜索的速度最快。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, half, m, g[50];
unsigned int w, ans, a[(1 << 24) + 1];

void dfs1(int i, unsigned int sum) {
	if (i == half) {
		a[++m] = sum;
		return;
	}
	dfs1(i + 1, sum);
	if (sum + g[i] <= w) dfs1(i + 1, sum + g[i]);
}

void calc(unsigned int val) {
	int rest = w - val;
	int l = 1, r = m;
	while (l < r) {
		int mid = (l + r + 1) / 2;
		if (a[mid] <= rest) l = mid; else r = mid - 1;
	}
	ans = max(ans, a[l] + val);
}

void dfs2(int i, unsigned int sum) {
	if (i == n + 1) {
		calc(sum);
		return;
	}
	dfs2(i + 1, sum);
	if (sum + g[i] <= w) dfs2(i + 1, sum + g[i]);
}

int main() {
	cin >> 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);
	half = n / 2 + 3;
	dfs1(1, 0);
	sort(a + 1, a + m + 1);
	m = unique(a + 1, a + m + 1) - (a + 1);
	dfs2(half, 0);
	cout << ans << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
unsigned int g[50], w, ans;
vector<unsigned int> a;

void dfs1(int k, unsigned int x) {
	if (!k) {
		a.push_back(x);
		return;
	}
	dfs1(k - 1, x);
	if (x + g[k] <= w) dfs1(k - 1, x + g[k]);
}

void dfs2(int i, unsigned int x) {
	if (i == n + 1) {
		int y = *--upper_bound(a.begin(), a.end(), w - x);
		ans = max(ans, x + y);
		return;
	}
	dfs2(i + 1, x);
	if (x + g[i] <= w) dfs2(i + 1, x + g[i]);
}

bool cmp(unsigned int x, unsigned int y) {
	return x > y;
}

int main() {
	cin >> w >> n;
	for (int i = 1; i <= n; i++) cin >> g[i];
	sort(g + 1, g + n + 1, cmp);
	int k = n / 2 + 3;
	dfs1(k - 1, 0);
	sort(a.begin(), a.end());
	m = unique(a.begin(), a.end()) - a.begin();
	dfs2(k, 0);
	cout << ans << endl;
	return 0;
}

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//3000ms
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 50;
int n, w, half;
int g[N];
int weight[1 << 25], idx;
int ans;

void dfs1(int now, int sum) {
  if (now == half) {
    weight[idx++] = sum;
    return;
  }
  // 不选当前第 now 个物品，sum 不变
  dfs1(now + 1, sum);
  
  // 选当前第 now 个物品，sum + g[now]
  if (1ll * sum + g[now] <= w) dfs1(now + 1, sum + g[now]);
}

void dfs2(int now, int sum) {
  if (now == n) {
    int l = 0, r = idx - 1;
    while (l < r) {
      int mid = l + r + 1 >> 1;
      if (weight[mid] <= w - sum) l = mid;
      else r = mid - 1;
    }
    ans = max(weight[l] + sum, ans);
    return;
  }
  
  dfs2(now + 1, sum);
  if (1ll * sum + g[now] <= w) dfs2(now + 1, sum + g[now]); 
}

int main() {
  cin >> w >> n;
  for (int i = 0; i < n; ++i) cin >> g[i];
  
  sort(g, g + n, [](int a, int b) { return a > b; });
  
  half = n / 2 + 2;

  dfs1(0, 0);

  sort(weight, weight + idx);
  idx = unique(weight, weight + idx) - weight;
  
  dfs2(half, 0);
  
  cout << ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 超时，8000ms
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 50;
int n, w, half;
int g[N];
int weight[1 << 25], idx;
int ans;

int main() {
  cin >> w >> n;
  for (int i = 0; i < n; ++i) cin >> g[i];
  
  sort(g, g + n, [](int a, int b) { return a > b; });
  
  half = n / 2 + 2;
  for (int i = 0; i < 1 << half; ++i) {
    bool flag = true;
    long long sum = 0;
    for (int j = 0; j < half; ++j) {
      if (i >> j & 1) sum += g[j]; 
      if (sum > w) {
        flag = false;
        break;
      }
    }
    if (flag) weight[idx++] = sum;
  } 

  sort(weight, weight + idx);
  idx = unique(weight, weight + idx) - weight;
  
  int r = n - half;
  
  for (int i = 0; i < 1 << r; ++i) {
    int sum = 0;
    bool flag = true;
    for (int j = 0; j < r; ++j) {
      if (i >> j & 1) sum += g[j + half];
      if (sum > w) {
        flag = false;
        break;
      }
    }
    if (flag) {
      int l = 0, r = idx - 1;
      while (l < r) {
        int mid = l + r + 1 >> 1;
        if (weight[mid] <= w - sum) l = mid;
        else r = mid - 1;
      }
      ans = max(weight[l] + sum, ans);
    }
  }
  
  cout << ans;
}