算法搜索

迭代加深加上各种剪枝方法

字数统计: 1.1k字   |   阅读时长: 4分

摘要: 迭代加深加各种剪枝手法，解决搜索难题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 迭代加深 中，我们详细介绍了迭代加深的思想。本文我们来解决一个艰难的问题，除了迭代加深，还需要各种剪枝手法。

170. 加成序列

满足如下条件的序列 $X$（序列中元素被标号为 $1, 2, \cdots, m$）被称为“加成序列”：

  1. $X[1]=1$
  2. $X[m]=n$
  3. $X[1] < X[2] < \cdots < X[m−1] < X[m]$
  4. 对于每个 $k (2\leq k\leq m)$ 都存在两个整数 $i$ 和 $j$($1\leq i,j\leq k−1$，$i$ 和 $j$ 可相等)，使得 $X[k]=X[i]+X[j]$。

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

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

1
2
3
4
5
6
7
8
9
10
11
输入格式
输入包含多组测试用例。
每组测试用例占据一行，包含一个整数 n。
当输入为单行的 0 时，表示输入结束。

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

数据范围
1<=n<=100

输入样例：
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

算法：迭代加深

依次填充序列 $X$ 中的每个位置 $k$，枚举 $i$ 和 $j$ 作为分支，将 $X[i] + X[j]$ 填到 $X[k]$ 上，然后递归地填写下一个位置。

如果上述 DFS 过程一路走到底，大致过程是每次选定一个分支，不断深入，直至到达递归边界才回溯。这样如果问题答案在某个较浅层的节点上，就会在不包含答案的深层子树上浪费很多时间。

对于当搜索树规模随着层的深入增长很快，且能确认答案在比较浅层的节点时，非常适合迭代加深。而本题通过样例以及一些自己在草稿纸上写的样例来看，答案都在浅层，也就是 $m$ 一般都不大。可以用迭代加深。也就是在 DFS 的过程中增加一个深度限制 depth。然后不断增加 depth，直至找到想要的答案。

DFS 中的剪枝

DFS 过程中需要多种剪枝方法，下面逐个来看。首先如果不做任何简直，则原始枚举如下：

1
2
for(int i = 0; i < m; ++i)
    for(int j = 0; j < m; ++j)

1. 等效性剪枝

枚举时候保持 i <= j：

1
2
for(int i = 0; i < m; ++i)
    for(int j = i; j < m; ++j)

2. 搜索顺序

从大到小搜索：

1
2
for(int i = m - 1; i >= 0; --i)
    for(int j = i; j >= 0; --j)

3. 可行性剪枝

发现不满足给定的限制条件时，提前回溯：

1
2
3
int nxt = result[i] + result[j];
if(nxt <= result.back() || nxt > n) 
    continue;

4. 最优性剪枝

形成下一个数 nxt = result[i] + result[j] 中，上一个数 result[m - 1] 必在其中。因为如果不在其中，则把 result[m-1] 去掉可以得到更好的答案。

1
2
for(int i = m - 1; i >= m - 1; --i)
    for(int j = i; j >= 0; --j)

代码 (C++)

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
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

bool dfs(vector<int>& result, int depth, int max_depth, int n)
{
    if(depth > max_depth)
        return false;
    if(n == result.back())
        return true;
    int m = result.size();
    for(int i = m - 1; i >= m - 1; --i)
    {
        for(int j = i; j >= 0; --j)
        {
            int nxt = result[i] + result[j];
            if(nxt <= result.back() || nxt > n) continue;
            result.push_back(nxt);
            if(dfs(result, depth + 1, max_depth, n))
                return true;
            result.pop_back();
        }
    }
    return false;
}

vector<int> solve(int n)
{
    vector<int> result(1, 1);
    int depth = 0; // 从 [0] 往前跳了 depth 步, result 中有 depth + 1 个元素
    while(!dfs(result, 0, depth, n))
    {
        ++depth;
        result.assign(1, 1);
    }
    return result;
}

int main()
{
    int n;
    while(cin >> n && n != 0)
    {
        vector<int> ans = solve(n);
        for(int i: ans)
            cout << i << " ";
        cout << endl;
    }
}
Share