IDA* ——启发式迭代加深搜索算法

A-star，迭代加深搜索以及 IDA-star#

我们先前在这篇文章中探讨了 A* 算法以及其实现思路。回顾一下，A* 算法为普通的搜索算法加上了一个名为估价函数的设置，使得 A* 能够在搜索时不会那么偏离正确答案（最短路径）。从而大幅改善了普通 BFS 的近似穷举的低效策略。

而迭代加深就有些“取巧”了。万一某一天，你碰到了一位出生很有底子的出题人。他出了一道搜索题，但是他故意设置了很多很深很深的子树用来卡你的 BFS 和 A*，这时你发现答案往往都在浅层，那么先前你的算法在深子树上做的一切工夫不就全白费了吗？于是迭代加深搜索应运而生，它限制每次搜索的最大深度，每次只从根节点开始向下搜索对应层数，若没找到答案，则继续加大最大深度；若找到了位于浅层的答案，直接返回，效率就会比普通的 BFS 与 A* 快不少。

而 IDA* 则是它的改进版，其中 ID 指 Iterative Deepening，即迭代加深。因此 IDA* 又叫做“迭代加深的 A* 算法”（启发式迭代加深搜索）。顾名思义，它将二者有机结合起来。每次限定一个最大深度向下搜索，配合来自 A* 的估价函数进行最优性剪枝，进一步提效。~~简直不要太爽~~。

迭代加深的执行效率#

有些人会问，每次加大迭代层数，程序都会从根节点重新开始扫描，那岂不是浪费了很多效率？

我们先从一个简单的完全二叉树开始分析：

根据完全二叉树的性质，搜素第一层需要扫描 ${1}$ 个节点（根节点）；第二层则需要扫描 ${4}$ 个节点；第三层是 ${8}$ 个……以此类推，第 $n$ 层就是 ${2^n}$ 个。根据等比数列的求和公式，搜索 $n$ 次，总共搜索了 ${2^n-1}$ 个节点（包含重复搜索）——其中前 $n-1$ 次的节点数共 ${2^{n-1}-1}$ 个，约为总数的一半。然而，实际题目中可能出现三叉树、四叉树等等多叉的树形结构。假设利用迭代加深思想搜索一颗满 $k$ 叉树，并令最大层数由 ${1}$ 迭代到 $n$ 一共需要搜索的节点数为 $f(n)$ 个（重复搜索也计入），那么随着 $k$ 的增大， $\frac{f(n-1)}{f(n)}$ 的值将越来越小，也就是说前面 $n-1$ 层搜索的复杂度在第 $n$ 次搜索的复杂度面前就相形见绌了，即 $\lim\limits_{k\to\infty}\frac{f(n-1)}{f(n)}=0$ 。迭代加深搜索的复杂度基本和搜索 $n_{max}$ 层的复杂度相差无几，因此以上的担心是没必要的。

典型例题#

洛谷 P10488 Booksort#

题目传送门：这里

题目难度：普及/提高+

给定 $n$ 本书，编号为 $1 \sim n$ 。
在初始状态下，书是任意排列的。
在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。
我们的目标状态是把书按照 $1 \sim n$ 的顺序依次排列。
求最少需要多少次操作。
输入：
第一行包含整数 $T$ ，表示共有 $T$ 组测试数据。
每组数据包含两行，第一行为整数 $n$ ，表示书的数量。
第二行为 $n$ 个整数，表示 $1 \sim n$ 的一种任意排列。
同行数之间用空格隔开。
输出：
每组数据输出一个最少操作次数。
如果最少操作次数大于或等于 $5$ 次，则输出 5 or more。
每个结果占一行。
数据范围
$1 \le n \le 15$

我们从什么地方看出需要使用 IDA*？首先，搜索空间较大：根据数据范围，书本最多有 ${15}$ 本，每次可以选择 ${1\sim14}$ 本任意插入其他位置，运用插空法，最大可能的状态总数就是 $C_{15}^1\times14+C_{15}^2\times13+\dots+C_{15}^{14}\times1\approx560^4$ ，严重超限；第二就是答案的位置浅：根据题目，当移动次数大于等于 ${5}$ 时就可以直接特判退出了，因此我们只需要在前 ${4}$ 层寻找答案即可。

既然是 IDA*，我们就需要设计估价函数。因为最终需要排成上升序列，每次操作最多更改一个地方的单调性。因此遍历给定的序列，当某个元素的后继节点不在本来的位置（表现为 $a_{i+1}\neq a_i+1$ ）时累加估价，返回即可。

对于状态搜索，考虑枚举每次移动的段的长度，然后在该段末尾至整个序列末尾的可插入位置中枚举段插入的位置，通过模拟得到插入后的序列即可。注意要及时恢复现场！

代码：

1
#include <bits/stdc++.h>
2

3
#define N 20
4

5
using namespace std;
6
typedef long long ll;
7

8
int n;
9
int a[N], cpy[5][N];
10

11
int f() {
12
    int res = 0;
13
    for (int i = 1; i < n; i++) {
14
        if (a[i] + 1 != a[i + 1]) res++;
15
    }
16
    return (int) ((res + 2) / 3);
17
}
18

19
void out() {
20
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
21
    cout << endl;
22
}
23

24
bool ida(int now, int max_d) {
25
    if (now + f() > max_d) return false;
26
    if (!f()) return true;
27
    for (int len = 1; len <= n; len++) { // 段长度
28
        for (int j = 1; j <= n - len + 1; j++) { // 段起始下标
29
            int seg_end = len + j - 1; // 段终止下标
30
            for (int k = seg_end + 1; k <= n; k++) { // 插入到下标k的元素后面
31
                memcpy(cpy[now], a, sizeof a);
32
                int y = j;
33
                for (int x = seg_end + 1; x <= k; x++, y++) a[y] = cpy[now][x];
34
                for (int x = j; x <= seg_end; x++, y++) a[y] = cpy[now][x];
35
                if (ida(now + 1, max_d)) return true;
36
                memcpy(a, cpy[now], sizeof cpy[now]);
37
            }
38
        }
39
    }
40
    return false;
41
}
42

43
int main() {
44
    ios::sync_with_stdio(false);
45
    cin.tie(nullptr);
46
    cout.tie(nullptr);
47

48
    int t;
49
    cin >> t;
50
    while (t--) {
51
        int dep = 0;
52
        cin >> n;
53
        for (int i = 1; i <= n; i++) cin >> a[i];
54
        while (!ida(0, dep) && dep < 5) dep++;
55
        if (dep == 5) cout << "5 or more" << endl;
56
        else cout << dep << endl;
57
    }
58

59
    return 0;
60
}

UVA 1343 The Rotation Game (旋转游戏)#

题目传送门：这里

题目难度：提高+/省选-

　　如图 ${1}$ 所示，有一个 “#” 形的棋盘，上面有 ${1,2,3}$ 三种数字各 $8$ 个。给定 $8$ 种操作，分别为图中的 $\text{A}\sim \text{H}$ 。这些操作会按照图中字母与箭头所指明的方向，把一条长度为 $8$ 的序列循环移动 $1$ 个单位。例如下图最左边的 “#” 形棋盘执行操作 $\text{A}$ 时，会变为图中间的 “#” 形棋盘，再执行操作 $\text{C}$ 后会变为图中最右边的 “#” 形棋盘。
现给定一个初始状态，请使用最少的操作次数，使 “#” 形棋盘最中间的 ${8}$ 个格子里的数字相同。
图1
输入格式：
输入包括不超过 ${30}$ 组测试数据。每个测试数据只包括一行，包含 ${24}$ 个整数，每相邻两个整数之间用 ${1}$ 个空格隔开，表示这个 “#” 形棋盘的初始状态。（这些整数的排列顺序是从上至下，同一行的从左至右。例如 $\text{1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3}$ 表示图 ${1}$ 最左边的状态。）每两组测试数据之间没有换行符。输入文件以一行 ${0}$ 结束。
输出格式：
　　对于每组测试数据，输出两行。第一行用字符 $\text{A}\sim \text{H}$ 输出操作的方法，每两个操作字符之间没有空格分开，如果不需要任何步数，输出 No moves needed。第二行输出最终状态中最中间的 ${8}$ 个格子里的数字。如果有多组解，输出操作次数最少的一组解；如果仍有多组解，输出字典序最小的一组。任意相邻两组测试数据的输出之间不需输出换行符。

这道题同样具有巨大的搜索空间，它的合法操作都有整整八种；但是答案可能位于较浅的层，具体表现在——每种操作若进行 ${6}$ 次，那么就相当于执行它的反操作一次，显然没有必要以小换大，应用到八种操作里，就是答案层数不会超过 ${48}$ 。因此可以以这点为硬限制进行迭代加深搜索。

观察到题目要求我们输出字典序最小的合法方案，只需要在搜索时按字典顺序循环搜索就好。对于剪枝，若上一次操作是将第三行整体向左滚动，那么当前层就显然不能将这一层向右滚动（~~滚了个寂寞~~）因此在函数签名里加上一个记录上一次操作的变量即可。

读入时为了直观（切合图中的结构），我选择使用二维数组存储 ${24}$ 个数字，但这也带来了不小的代码量（~~逆天条件判断，我一开始用 switch 语句代码更长~~）。

1
#include <bits/stdc++.h>
2

3
#define N 10
4
using namespace std;
5

6
int a[N][N], cpy[55][N][N];
7
char seq[55];
8

9
int f() {
10
    int cnt[4];
11
    memset(cnt, 0, sizeof cnt);
12
    for (int i = 3; i <= 5; i++) cnt[a[3][i]]++, cnt[a[5][i]]++;
13
    cnt[a[4][3]]++, cnt[a[4][5]]++;
14
    return 8 - max(max(cnt[1], cnt[2]), cnt[3]);
15
}
16

17
bool check() {
18
    int piv = a[3][3];
19
    return (a[3][4] == piv && a[3][5] == piv && a[4][3] == piv && a[4][5] == piv && a[5][3] == piv && a[5][4] == piv &&
20
            a[5][5] == piv);
21
}
22

23
void vertical_scroll(bool lCol, bool up) {
24
    if (lCol) {
25
        if (up) for (int i = 1; i < 7; i++) swap(a[i][3], a[i + 1][3]);
26
        else for (int i = 7; i > 1; i--) swap(a[i][3], a[i - 1][3]);
27
    } else {
28
        if (up) for (int i = 1; i < 7; i++) swap(a[i][5], a[i + 1][5]);
29
        else for (int i = 7; i > 1; i--) swap(a[i][5], a[i - 1][5]);
30
    }
31
}
32

33
void horizontal_scroll(bool uRow, bool left) {
34
    if (uRow) {
35
        if (left) for (int i = 1; i < 7; i++) swap(a[3][i], a[3][i + 1]);
36
        else for (int i = 7; i > 1; i--) swap(a[3][i], a[3][i - 1]);
37
    } else {
38
        if (left) for (int i = 1; i < 7; i++) swap(a[5][i], a[5][i + 1]);
39
        else for (int i = 7; i > 1; i--) swap(a[5][i], a[5][i - 1]);
40
    }
41
}
42

43
void operate(char op) {
44
    switch (op) {
45
        case 'A':
46
        case 'B':
47
        case 'E':
48
        case 'F':
49
            vertical_scroll((op == 'A' || op == 'F'), (op == 'A' || op == 'B'));
50
            break;
51
        default:
52
            horizontal_scroll((op == 'C' || op == 'H'), (op == 'H' || op == 'G'));
53
            break;
54
    }
55
}
56

57
bool ida(int now, int max_dep, char last) {
58
    if (now + f() > max_dep) return false;
59
    if (check()) return true;
60
    for (int i = 0; i <= 7; i++) {
61
        if (now && last != '\0') {
62
            if (last == 'A' && i == 5) continue;
63
            if (last == 'F' && i == 0) continue;
64
            if (last == 'B' && i == 4) continue;
65
            if (last == 'E' && i == 1) continue;
66
            if (last == 'C' && i == 7) continue;
67
            if (last == 'H' && i == 2) continue;
68
            if (last == 'D' && i == 6) continue;
69
            if (last == 'G' && i == 3) continue;
70
        }
71
        memcpy(cpy[now], a, sizeof a);
72
        operate((char) (i + 'A'));
73
        seq[now] = (char) (i + 'A');
74
        if (ida(now + 1, max_dep, (char) (i + 'A'))) return true;
75
        memcpy(a, cpy[now], sizeof cpy[now]);
76
    }
77
    return false;
78
}
79

80
int main() {
81
    ios::sync_with_stdio(false);
82
    cin.tie(nullptr);
83
    cout.tie(nullptr);
84

85
    int x = 0, cnt = 0;
86
    while (cin >> x && x) {
87
        cnt++;
88
        if (cnt == 25) {
89
            cnt = 1;
90
            memset(seq, 0, sizeof seq);
91
        }
92

93
        if (cnt == 1) a[1][3] = x;
94
        else if (cnt == 2) a[1][5] = x;
95
        else if (cnt == 3) a[2][3] = x;
96
        else if (cnt == 4) a[2][5] = x;
97
        else if (cnt == 12) a[4][3] = x;
98
        else if (cnt == 13) a[4][5] = x;
99
        else if (cnt == 21) a[6][3] = x;
100
        else if (cnt == 22) a[6][5] = x;
101
        else if (cnt == 23) a[7][3] = x;
102
        else if (cnt == 24) a[7][5] = x;
103
        else if (cnt >= 5 && cnt <= 11) a[3][cnt - 4] = x;
104
        else if (cnt >= 14 && cnt <= 20) a[5][cnt - 13] = x;
105

106
        if (cnt == 24) {
107
            if (check()) cout << "No moves needed" << endl;
108
            else {
109
                int dep = 1;
110
                while (!ida(0, dep, '\0') && dep < 50) dep++;
111
                cout << seq << endl;
112
            }
113
            cout << a[3][3] << endl;
114
        }
115
    }
116
    return 0;
117
}

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

IDA* ——启发式迭代加深搜索算法

A-star，迭代加深搜索以及 IDA-star#

迭代加深的执行效率#

典型例题#

洛谷 P10488 Booksort#

UVA 1343 The Rotation Game (旋转游戏)#

支持与分享

评论区

音乐

目录

音乐

JustPureH2O

穷方圆平直之情，尽规矩准绳之用

音乐

IDA* ——启发式迭代加深搜索算法

A-star，迭代加深搜索以及 IDA-star#

迭代加深的执行效率#

典型例题#

洛谷 P10488 Booksort#

UVA 1343 The Rotation Game (旋转游戏)#

支持与分享

评论区

音乐

目录

JustPureH₂O