算法竞赛进阶指南 搜索 0x28 IDA*

在上一节中我们提到，A*算法本质上是带有估价函数的优先队列BFS算法，故A*算法有一个显而易见的缺点，就是需要维护一个二叉堆（优先队列）来存储状态及其估价，耗费空间较大，并且对堆进行一次操作也要花费$O(logN)$的时间

我们也提到了A*算法的关键在于设计估价函数。既然估价函数与优先队列BFS结合可以产生A*算法，那么估价函数能否与DFS结合呢？当然，DFS也有一个缺点，就是一旦估价出现失误，容易向下递归深入一个不能产生最优解的分支，浪费许多时间

综合以上讨论，我们最终选择把估价函数与迭代加深的DFS算法相结合。请读者回忆0x24节中学习的迭代加深DFS算法。该算法限定一个深度，在不超过该深度的前提下执行DFS，若找不到解就扩大深度限制，重新进行搜索

我们设计一个估价函数，估算从每个状态到目标状态需要的步数。当然，与A*算法一样，估价函数需要遵守“估计值不大于未来实际步数”的准则。然后，以迭代加深DFS的搜索框架为基础，把原来简单的深度限制加强为：若当前深度+未来估计步数 > 深度限制，则立即从当前分支回溯

这就是IDA*算法（迭代加深的A*算法）。IDA*算法在许多场景下表现出了优秀的效率，并且程序实现的难度低于A*算法。

1、AcWing 180. 排书

题意 ：

• 给定 n 本书，编号为 1∼n。在初始状态下，书是任意排列的。
• 在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。
• 我们的目标状态是把书按照 1∼n 的顺序依次排列。
• 求最少需要多少次操作。
• 如果最少操作次数大于或等于 5 次，则输出 5 or more。
• 1≤n≤15

思路 ：

• 我们先来估算一下每个状态的分支数量。在每个状态下，我们可以抽取连续的一段书，移动到另一个位置。对于任意整数i，当抽取长度为i时，有n - i + 1种选择方法，有n - i个可插入的位置。另外，把一段书移动到更靠前的某个位置，等价于把“跳过”的那段书移动到靠后的某个位置，所以上面的计算方法把每种移动情况算了两遍。每个状态的分支数量约为：${\sum }_{i=1}^n(n-i)\ast (n-i+1)\le (15\ast 14+14\ast 13+...+2\ast 1)/2=560$
• 根据题目要求，我们只需要考虑在4次操作以内是否能实现目标，也就是我们只需要考虑搜索树的前4层。4层的搜索树的规模能够达到${560}^4$，无法承受
• 第一种解法是采用双向BFS，从起始状态、目标状态开始各搜索2步，看能够到达相同的状态进行衔接，复杂度降低为${560}^2$
• 第二种解法是采用IDA*：
• 在目标状态下，第i本书后边应该是第i + 1本书，我们称i + 1是i的正确后继
• 对于任意状态，考虑整个排列中书的错误后继的总个数（记为tot），可以发现每次操作至多更改3本书的后继。即使在最理想的情况下，每次操作都能把某3个错误后继全部改对，消除所有错误后继的操作次数也至少需要$\lceil tot/3\rceil$（向上取整）次（即$\frac{tot+2}{3}$）
• 因此，我们把一个状态s的估价函数设计为$f(s)=\lceil tot/3\rceil$，其中tot表示在状态s下书的错误后继总数
• 我们采用迭代加深的方法，从1～4依次限制搜索深度，然后从起始状态出发开始DFS。DFS时，在每个状态下直接枚举抽取哪一段、移动到更靠后的哪个位置，沿着该分支深入即可。注意在进入任何状态s后，我们先进行判断，如果当前操作次数加上f(s)已经大于深度限制，直接从当前分支回溯。在实际测试中，上述IDA*算法能够比双向BFS更快地求出答案。
• 理论上最多搜索 ${560}^4$ 个状态，使用IDA*后实际搜索的状态数量很少。

#include 
#include 
using namespace std;
const int N = 20;

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 = l, y = r + 1; y <= k; ++ x, ++ y) q[x] = w[depth][y];
                for (y = l; y <= r; ++ x, ++ y) q[x] = w[depth][y];
                if (dfs(depth + 1, max_depth)) return true;
                memcpy(q, w[depth], sizeof q);
            }
        }
    }
    return false;
}

int main() {
    int _; scanf("%d", &_);
    while (_ -- ) {
        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);
    }
}
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

AcWing 181. 回转游戏

题意 ：

• 每个测试用例占一行，包含 24 个数字，表示将初始棋盘中的每一个位置的数字，按整体从上到下，同行从左到右的顺序依次列出。
• 每个测试用例输出占两行。
• 第一行包含所有移动步骤，每步移动用大写字母 A∼H 中的一个表示，字母之间没有空格，如果不需要移动则输出 No moves needed。
• 第二行包含一个整数，表示移动完成后，中间 8 个格子里的数字。
• 如果有多种方案，则输出字典序最小的解决方案。

思路 ：

• 可以使用IDA*算法求解。首先我们来确定DFS的框架——在每个状态下枚举执行哪种操作，然后沿着该分支深入即可。有一个很明显的剪枝是记录上一次的操作，不执行上次操作的逆操作，避免来回搜索
• 接下来我们设计估值函数。通过仔细观察可以发现，在每个状态下，如果中间8个格子里出现次数最多的数字是k，而中间8个格子里剩下的数字有m个与k不同，那么把中间8个格子里的数字都变为k至少需要m次操作。因此，我们就以这个m为估价即可
• 总而言之，我们采用迭代加深，由1开始从小到大依次限制操作次数（搜索深度），在DFS的每个状态下，若“当前操作次数+估价>深度限制“，则从当前分支回溯

#include 
#include 
using namespace std;
const int N = 24;

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 q[N];
int path[100];
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
int opposite[] = {5, 4, 7, 6, 1, 0, 3, 2};

int f() {
    static int sum[4];
    memset(sum, 0, sizeof sum);
    for (int i = 0; i < 8; ++ i) sum[q[center[i]]] ++ ;
    int mx = 0;
    for (int i = 1; i <= 3; ++ i) mx = max(mx, sum[i]);
    return 8 - mx;
}
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]);
        puts("");
        printf("%d\n", q[6]);
    }
}

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
61
62
63
64
65
66