信息学奥赛算法练功房◌检测中
阶段 3 · 搜索　·　第 18 章提高组 S

迭代加深与双向 BFS

BFS 快但费内存，DFS 省内存但不保证最短。这一章的两个工具，各拿走一半的好处。

需要先学：第 15 章 BFS 变形：多源 BFS 与状态图搜索、第 16 章 DFS 剪枝：可行性、最优性、搜索顺序例题：八数码（继续）建议用时：110 分钟
阶段 3 的收官章

第 14、15 章的 BFS 有个躲不掉的毛病：它必须把所有到过的状态记在一张表里。

八数码只有 36 万个状态，撑得住。可一旦状态空间上亿（十五数码、魔方、 或者任何一道「状态是一串数字」的题），那张表就装不下了。

这一章的两个工具分别对付两个问题：

工具 解决什么 代价
迭代加深（IDDFS） 内存 —— 只要一个递归栈 会重复搜前面的层
双向 BFS 时间 —— 把搜索深度砍一半 必须知道终点是什么

题目继续用第 15 章那个八数码，这样能直接对比。

1回顾：单向 BFS 的代价

bfs.cpp单向 BFS（对照组）
这是第 15 章那份，搬过来当基准。这个局面要 18 步。
// 八数码 —— 单向 BFS（第 15 章那份，搬过来当对照组）
//
// 输入：一行 9 个数字（0 是空格）
// 输出：最少几步能拼成 123804765；无解输出 -1
//
// 它是对的、也不慢，但有一个躲不掉的毛病：**内存**。
// BFS 必须把「所有到过的状态」记在一张表里，否则会绕圈子。
// 八数码只有 36 万个状态还撑得住，可一旦状态空间大到上亿（十五数码、魔方），
// 这张表就装不下了。
//
// 这一章的两个工具，就是分别对付「内存」和「时间」这两个问题的：
//     迭代加深 —— 几乎不用内存（只要一个递归栈）
//     双向 BFS —— 把搜索树的深度砍一半


#include <bits/stdc++.h>
using namespace std;


const string GOAL = "123804765";


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    string s;
    if (!(cin >> s)) return 0;
    if (s.size() != 9) { cout << -1 << "\n"; return 0; }
    if (s == GOAL) { cout << 0 << "\n"; return 0; }


    unordered_map<string, int> dist;
    dist.reserve(1 << 16);
    queue<string> q;
    dist[s] = 0;
    q.push(s);


    const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};
    while (!q.empty()) {
        string cur = q.front(); q.pop();
        int d = dist[cur];
        int p = (int)cur.find('0'), i = p / 3, j = p % 3;


        for (int t = 0; t < 4; t++) {
            int x = i + di[t], y = j + dj[t];
            if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;
            string nxt = cur;
            swap(nxt[p], nxt[x * 3 + y]);
            if (dist.count(nxt)) continue;
            dist[nxt] = d + 1;
            if (nxt == GOAL) { cout << d + 1 << "\n"; return 0; }
            q.push(nxt);
        }
    }
    cout << -1 << "\n";
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

它没错也不慢，问题在那张 unordered_map：状态越多，内存越大。 后面会看到具体数字。

2★ 迭代加深：限定深度的 DFS，一层层放开

★ 关键的一步

做法：只往下搜到第 limit 层，到了就掉头。 limit 从 0 开始一层层往上加，第一次搜到目标时，limit 就是最短步数。

for (limit = 0; limit <= 上限; limit++)
    if (dfs(0)) { 答案就是 limit; break; }

bool dfs(int depth) {
    if (到目标) return true;
    if (depth >= limit) return false;    // ← 就这一句，DFS 变成迭代加深
    for (每个选择) { 进入; if (dfs(depth+1)) return true; 撤销; }
    return false;
}

它同时拿到了两边的好处：

  • 像 DFS 一样省内存 —— 只有一个递归栈，几十个字节，没有任何判重表
  • 像 BFS 一样保证最短 —— 因为深度是一层层放开的，浅的解一定先被找到
★ 「每次都重头搜一遍」不亏吗

每加一层，前面所有层都要重搜 —— 听着浪费得离谱。算一笔账：

设每个状态平均能扩展出 b 个新状态（八数码大约 2~3）。

深度 d 那一层：            b^d 个节点
前面所有层加起来：  1 + b + b² + … + b^(d-1) ≈ b^d / (b-1)

b = 3 时，前面全部重搜的总量还不到最后一层的一半。

指数增长下，最后一层就占了绝大多数 —— 前面重来几遍根本无所谓。 这条性质对所有指数级搜索都成立，值得记死。

iddfs.cpp迭代加深
// 八数码 —— 迭代加深 DFS（IDDFS）
//
// 输入输出和 bfs.cpp 完全一样。
//
// ============ 迭代加深是什么 ============
//
// 「限定深度的 DFS」：只往下搜到第 limit 层，到了就掉头。
// limit 从 0 开始，一层层往上加：0 搜不到就试 1，1 搜不到就试 2……
// **第一次搜到目标时，limit 就是最短步数。**
//
// 它同时拿到了 DFS 和 BFS 的好处：
//     像 DFS 一样省内存（只要一个递归栈，几十个字节）
//     像 BFS 一样保证最短（因为是按深度一层层放开的）
//
// ============ 「重复搜」不是很亏吗 ============
//
// 每加一层，前面所有层都要重搜一遍 —— 听起来浪费得离谱。但算一笔账：
//
// 设每个状态平均能扩展出 b 个新状态（八数码 b ≈ 2~3）。
//     深度 d 的那一层有 b^d 个节点
//     前面所有层加起来是 1 + b + b² + … + b^(d-1) ≈ b^d / (b-1)
//
// 也就是说，**重复搜的总量还不到最后一层的一半**（b = 3 时约 1/2）。
// 指数增长下，最后一层就占了绝大多数 —— 前面重来几遍根本无所谓。
//
// **这是所有指数级搜索共有的性质，值得记住。**
//
// ============ 两个细节 ============
//
// 1. 不能走回头路（`(t ^ 1) == prevMove` 那一句）：
//    刚把空格往右挪，下一步又往左挪回来，等于原地打转。
//    0/1 是上/下，2/3 是左/右，所以异或 1 正好是反方向。
//
// 2. 深度上限 24：八数码的最优解最多 31 步，但配套的生成器只造浅局面，
//    24 层足够了。加这个上限是为了让无解数据不至于跑到天荒地老。


#include <bits/stdc++.h>
using namespace std;


const string GOAL = "123804765";
string cur;
int limitDepth;
const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};


bool dfs(int depth, int prevMove) {
    if (cur == GOAL) return true;
    if (depth >= limitDepth) return false;          // 到达深度上限，掉头


    int p = (int)cur.find('0'), i = p / 3, j = p % 3;
    for (int t = 0; t < 4; t++) {
        if (prevMove >= 0 && (t ^ 1) == prevMove) continue;   // 不走回头路
        int x = i + di[t], y = j + dj[t];
        if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;


        swap(cur[p], cur[x * 3 + y]);
        if (dfs(depth + 1, t)) return true;
        swap(cur[p], cur[x * 3 + y]);               // 撤销
    }
    return false;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    if (!(cin >> cur)) return 0;
    if (cur.size() != 9) { cout << -1 << "\n"; return 0; }


    for (limitDepth = 0; limitDepth <= 24; limitDepth++)
        if (dfs(0, -1)) { cout << limitDepth << "\n"; return 0; }


    cout << -1 << "\n";
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
⚠ 一个必须写的小细节：不走回头路
if (prevMove >= 0 && (t ^ 1) == prevMove) continue;

刚把空格往右挪，下一步又往左挪回来 —— 等于原地打转，白白浪费一层深度。 （0/1 是上/下，2/3 是左/右，所以异或 1 正好是反方向。）

迭代加深没有判重表，所以这种「一步就绕回来」的浪费必须手动挡掉。 这也是它和 BFS 最大的取舍：省了内存，就得自己小心重复。

3★ 再进一步：IDA* —— 给迭代加深装一个估价函数

★ 关键的一步

迭代加深还有个明显的浪费：明明离目标还差十万八千里，它还在傻乎乎往下搜， 非要撞上深度上限才掉头。

如果能估计「从现在这个局面出发，至少还要走多少步」（记作 h），就能提前掐掉：

if (g + h() > limit) return false;      // 已经走了 g 步，至少还要 h 步 —— 本轮不可能走通

这就是第 16 章第 9 步提到的估价函数，也是 A* 家族的核心。

这道题用的估价：曼哈顿距离。 每个数字块「离它该在的位置」还差几格（横向差 + 纵向差），全部加起来。

为什么它是「至少还要走的步数」？因为每走一步只有一个块动一格， 它的曼哈顿距离最多减 1。要把总距离降到 0，至少需要那么多步。

⚠ 估价函数绝对不能高估

专业说法叫「可接纳」（admissible）。

一旦估多了，就可能把真正的最优解剪掉 —— 那不是剪枝，是剪错了。 （第 16 章那句话：剪枝不该改变答案。）

所以估价函数宁可保守。曼哈顿距离是安全的：它连「其他块挡路」都没算进去， 实际步数只会更多，不会更少。

ida.cppIDA*
和 iddfs.cpp 比，只多了一个 h() 函数和一句判断。效果见下一步那张表。
// 八数码 —— IDA*（迭代加深 + 估价函数）
//
// 输入输出和前两份完全一样。
//
// ============ 只比 iddfs.cpp 多了一个函数 ============
//
// 迭代加深有个明显的浪费：明明离目标还差十万八千里，它还在傻乎乎地往下搜，
// 直到撞上深度上限才掉头。
//
// 如果能**估计**出「从现在这个局面出发，至少还要走多少步」，
// 就可以提前掐掉：
//
//     已经走了 g 步 + 至少还要 h 步 > 深度上限  →  这条路不可能在本轮走通，直接返回
//
// 这就是**估价函数**（第 16 章第 9 步提过的那个东西），也是 A* 家族的核心。
//
// ============ 这里用的估价：曼哈顿距离 ============
//
// 每个数字块「离它该在的位置」还差几格（横向差 + 纵向差），全部加起来。
//
// 为什么它是「至少还要走的步数」？
//   每走一步，只有一个数字块移动一格，它的曼哈顿距离最多减 1。
//   所以要把总距离降到 0，**至少**需要「总距离」那么多步。
//
// ⚠ 估价函数必须**不高估**（专业说法叫「可接纳」）。
//   一旦估多了，就可能把真正的最优解剪掉 —— 那就不是剪枝，是剪错了。
//   （回想第 16 章那句话：剪枝不该改变答案。）
//
// 效果：局面越深，IDA* 越占便宜。跑一下 count.cpp 看具体数字。


#include <bits/stdc++.h>
using namespace std;


const string GOAL = "123804765";
string cur;
int limitDepth;
int goalPos[256];                     // goalPos['5'] = '5' 在目标里的下标
const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};


/** 曼哈顿距离之和：至少还要走这么多步 */
int h() {
    int s = 0;
    for (int p = 0; p < 9; p++) {
        char c = cur[p];
        if (c == '0') continue;       // 空格不算
        int q = goalPos[(int)c];
        s += abs(p / 3 - q / 3) + abs(p % 3 - q % 3);
    }
    return s;
}


bool dfs(int g, int prevMove) {
    int est = h();
    if (est == 0) return true;                  // 已经到目标
    if (g + est > limitDepth) return false;     // ★ 估价剪枝：本轮不可能走通


    int p = (int)cur.find('0'), i = p / 3, j = p % 3;
    for (int t = 0; t < 4; t++) {
        if (prevMove >= 0 && (t ^ 1) == prevMove) continue;
        int x = i + di[t], y = j + dj[t];
        if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;


        swap(cur[p], cur[x * 3 + y]);
        if (dfs(g + 1, t)) return true;
        swap(cur[p], cur[x * 3 + y]);
    }
    return false;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    if (!(cin >> cur)) return 0;
    if (cur.size() != 9) { cout << -1 << "\n"; return 0; }


    for (int p = 0; p < 9; p++) goalPos[(int)GOAL[p]] = p;


    // 起手的深度上限直接从 h() 开始 —— 比它小的层数根本不可能有解
    for (limitDepth = h(); limitDepth <= 40; limitDepth++)
        if (dfs(0, -1)) { cout << limitDepth << "\n"; return 0; }


    cout << -1 << "\n";
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

4★ 双向 BFS：两头一起搜

★ 关键的一步

单向 BFS 要铺开一棵深度 d 的树，节点数约 b^d。

如果从起点和终点同时往中间搜，两边各铺 d/2 层就会撞上：

单向：  b^d
双向：  2 · b^(d/2)

b = 3、d = 20 时：

单向：3²⁰ ≈ 35 亿
双向：2 × 3¹⁰ ≈ 12 万

快了三万倍。这不是常数优化 —— 它把指数砍了一半。

三个实现要点：

  1. 每次扩展节点少的那一边，让两棵树长得均衡。
  2. 相遇判定：新扩展出的状态如果在对面那张表里，答案 = 这边步数 + 对面步数。
  3. 必须整层整层地扩，否则可能先撞上一条不是最短的路径。
⚠ 双向 BFS 的前提：终点必须是明确知道的

「求最少步数到某个确定状态」→ 可以用。

「求最少步数到任意一个满足某条件的状态」→ 不行，你没法从终点倒着搜。

这个限制很实在。拿到题先确认「终点是不是唯一且已知」，再决定用不用它。

bibfs.cpp双向 BFS
// 八数码 —— 双向 BFS
//
// 输入输出和前几份完全一样。
//
// ============ 关键的一步：两头一起搜 ============
//
// 单向 BFS 要铺开一棵深度为 d 的树，节点数约 b^d。
//
// 但如果**从起点和终点同时往中间搜**，两边各铺开 d/2 层就会撞上：
//
//     b^(d/2) + b^(d/2) = 2·b^(d/2)
//
// 举个具体的：b = 3、d = 20 时
//     单向：3²⁰ ≈ 35 亿
//     双向：2 × 3¹⁰ ≈ 12 万
// **快了三万倍。** 这不是常数优化，是把指数砍了一半。
//
// ============ 实现要点 ============
//
// 1. **每次扩展节点少的那一边。**这样两棵树长得均衡，效果最好。
// 2. **相遇判定**：新扩展出的状态如果在对面那张表里出现过，
//    答案就是 `这边的步数 + 对面的步数`。
// 3. **必须整层整层地扩**（一次把队列里当前这一层全处理完），
//    否则可能先撞上一条不是最短的路径。
//
// ⚠ 双向 BFS 的前提：**终点必须是明确知道的**。
//   「求最少步数到某个确定状态」可以用；
//   「求最少步数到任意一个满足某条件的状态」就不行 —— 你没法从终点倒着搜。


#include <bits/stdc++.h>
using namespace std;


const string GOAL = "123804765";
const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};


/** 把 q 这一层整层扩展一次；如果撞上了 other，返回总步数，否则返回 -1 */
int expandLayer(queue<string>& q, unordered_map<string, int>& mine,
                unordered_map<string, int>& other) {
    int sz = (int)q.size();
    for (int c = 0; c < sz; c++) {
        string cur = q.front(); q.pop();
        int d = mine[cur];
        int p = (int)cur.find('0'), i = p / 3, j = p % 3;


        for (int t = 0; t < 4; t++) {
            int x = i + di[t], y = j + dj[t];
            if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;
            string nxt = cur;
            swap(nxt[p], nxt[x * 3 + y]);


            if (mine.count(nxt)) continue;              // 自己这边走过了
            auto it = other.find(nxt);
            if (it != other.end()) return d + 1 + it->second;   // ★ 撞上了


            mine[nxt] = d + 1;
            q.push(nxt);
        }
    }
    return -1;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    string s;
    if (!(cin >> s)) return 0;
    if (s.size() != 9) { cout << -1 << "\n"; return 0; }
    if (s == GOAL) { cout << 0 << "\n"; return 0; }


    unordered_map<string, int> da, db;      // 分别记「离起点多远」「离终点多远」
    queue<string> qa, qb;
    da[s] = 0; qa.push(s);
    db[GOAL] = 0; qb.push(GOAL);


    while (!qa.empty() && !qb.empty()) {
        // 总是先扩展小的那一边
        int got = (qa.size() <= qb.size()) ? expandLayer(qa, da, db)
                                           : expandLayer(qb, db, da);
        if (got >= 0) { cout << got << "\n"; return 0; }
    }


    cout << -1 << "\n";
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

5★ 四种方法，同一个局面，工作量并排数出来

count.cpp四种方法对比
换几个不同深度的局面跑跑看，四种方法的强弱会随深度变化。
// 四种搜索方式，同一个局面，工作量并排数出来
//
// 输入：一行 9 个数字
// 输出：单向 BFS / 双向 BFS / 迭代加深 / IDA* 各自访问了多少节点、用了多久、
//       以及各自要记住多少个状态（内存）
//
// 这张表是这一章的核心。要看的有两件事：
//
//   1. **双向 BFS 的节点数** 大约是单向的平方根级别 —— 深度砍一半的直接后果。
//   2. **迭代加深和 IDA* 记住的状态数是 0** —— 它们只有一个递归栈。
//      时间上迭代加深可能比 BFS 还慢（毕竟要重复搜），
//      但**它能解决那些 BFS 内存爆掉的题**，这是本质区别。
//
// 换几个不同深度的局面跑一跑（浅的、深的），四种方法的强弱会随深度变化 ——
// 这也是要体会的：**没有哪个方法永远最好。**


#include <bits/stdc++.h>
using namespace std;


const string GOAL = "123804765";
const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};


long long nodes;


/* ------------------------------ 单向 BFS ------------------------------ */
int runBfs(const string& s, long long& visited) {
    if (s == GOAL) { visited = 1; return 0; }
    unordered_map<string, int> dist;
    queue<string> q;
    dist[s] = 0; q.push(s);
    nodes = 0;


    while (!q.empty()) {
        string cur = q.front(); q.pop();
        nodes++;
        int d = dist[cur], p = (int)cur.find('0'), i = p / 3, j = p % 3;
        for (int t = 0; t < 4; t++) {
            int x = i + di[t], y = j + dj[t];
            if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;
            string nxt = cur;
            swap(nxt[p], nxt[x * 3 + y]);
            if (dist.count(nxt)) continue;
            dist[nxt] = d + 1;
            if (nxt == GOAL) { visited = (long long)dist.size(); return d + 1; }
            q.push(nxt);
        }
    }
    visited = (long long)dist.size();
    return -1;
}


/* ------------------------------ 双向 BFS ------------------------------ */
int expandLayer(queue<string>& q, unordered_map<string, int>& mine,
                unordered_map<string, int>& other) {
    int sz = (int)q.size();
    for (int c = 0; c < sz; c++) {
        string cur = q.front(); q.pop();
        nodes++;
        int d = mine[cur], p = (int)cur.find('0'), i = p / 3, j = p % 3;
        for (int t = 0; t < 4; t++) {
            int x = i + di[t], y = j + dj[t];
            if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;
            string nxt = cur;
            swap(nxt[p], nxt[x * 3 + y]);
            if (mine.count(nxt)) continue;
            auto it = other.find(nxt);
            if (it != other.end()) return d + 1 + it->second;
            mine[nxt] = d + 1;
            q.push(nxt);
        }
    }
    return -1;
}


int runBiBfs(const string& s, long long& visited) {
    if (s == GOAL) { visited = 2; return 0; }
    unordered_map<string, int> da, db;
    queue<string> qa, qb;
    da[s] = 0; qa.push(s);
    db[GOAL] = 0; qb.push(GOAL);
    nodes = 0;


    while (!qa.empty() && !qb.empty()) {
        int got = (qa.size() <= qb.size()) ? expandLayer(qa, da, db) : expandLayer(qb, db, da);
        if (got >= 0) { visited = (long long)(da.size() + db.size()); return got; }
    }
    visited = (long long)(da.size() + db.size());
    return -1;
}


/* ---------------------------- 迭代加深 / IDA* ---------------------------- */
string cur;
int limitDepth;
int goalPos[256];
bool useH;


int hVal() {
    int s = 0;
    for (int p = 0; p < 9; p++) {
        char c = cur[p];
        if (c == '0') continue;
        int q = goalPos[(int)c];
        s += abs(p / 3 - q / 3) + abs(p % 3 - q % 3);
    }
    return s;
}


bool dfs(int g, int prevMove) {
    nodes++;
    if (cur == GOAL) return true;
    if (useH) { if (g + hVal() > limitDepth) return false; }
    else if (g >= limitDepth) return false;


    int p = (int)cur.find('0'), i = p / 3, j = p % 3;
    for (int t = 0; t < 4; t++) {
        if (prevMove >= 0 && (t ^ 1) == prevMove) continue;
        int x = i + di[t], y = j + dj[t];
        if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;
        swap(cur[p], cur[x * 3 + y]);
        if (dfs(g + 1, t)) return true;
        swap(cur[p], cur[x * 3 + y]);
    }
    return false;
}


int runDeepening(const string& s, bool withH) {
    cur = s;
    useH = withH;
    nodes = 0;
    int start = withH ? hVal() : 0;
    for (limitDepth = start; limitDepth <= 30; limitDepth++) {
        cur = s;
        if (dfs(0, -1)) return limitDepth;
    }
    return -1;
}


int main() {
    string s;
    if (!(cin >> s)) return 0;
    if (s.size() != 9) { cout << "请输入 9 个数字（0 表示空格）\n"; return 0; }
    for (int p = 0; p < 9; p++) goalPos[(int)GOAL[p]] = p;


    cout << "局面 " << s << "　目标 " << GOAL << "\n\n";
    cout << "方法              答案      展开的节点数     记住的状态数      耗时(ms)\n";
    cout << "--------------  ------  ---------------  ---------------  ------------\n";


    auto row = [&](const char* name, int ans, long long nd, long long mem, double ms) {
        cout << name << setw(8) << ans << setw(17) << nd << setw(17) << mem
             << setw(14) << fixed << setprecision(2) << ms << "\n";
    };


    {
        long long mem = 0;
        auto t0 = chrono::steady_clock::now();
        int ans = runBfs(s, mem);
        auto t1 = chrono::steady_clock::now();
        row("单向 BFS      ", ans, nodes, mem, chrono::duration<double, milli>(t1 - t0).count());
    }
    {
        long long mem = 0;
        auto t0 = chrono::steady_clock::now();
        int ans = runBiBfs(s, mem);
        auto t1 = chrono::steady_clock::now();
        row("双向 BFS      ", ans, nodes, mem, chrono::duration<double, milli>(t1 - t0).count());
    }
    {
        auto t0 = chrono::steady_clock::now();
        int ans = runDeepening(s, false);
        auto t1 = chrono::steady_clock::now();
        row("迭代加深      ", ans, nodes, 0, chrono::duration<double, milli>(t1 - t0).count());
    }
    {
        auto t0 = chrono::steady_clock::now();
        int ans = runDeepening(s, true);
        auto t1 = chrono::steady_clock::now();
        row("IDA*（曼哈顿）", ans, nodes, 0, chrono::duration<double, milli>(t1 - t0).count());
    }


    cout << "\n「记住的状态数」那一列就是内存开销的来源。\n";
    cout << "迭代加深和 IDA* 是 0 —— 它们只有一个递归栈，这是它们最大的价值。\n";
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

本机实测（局面 845201376，最优 18 步）：

方法 答案 展开的节点数 记住的状态数 耗时
单向 BFS 18 19 437 29 446 14.53 毫秒
双向 BFS 18 557 901 0.38 毫秒
迭代加深 18 190 706 0 3.48 毫秒
IDA*（曼哈顿） 18 149 0 0.01 毫秒
★ 这张表要读出三件事

1. 「记住的状态数」那一列就是内存。 迭代加深和 IDA* 是 0 —— 它们只有一个递归栈。 这是它们存在的全部理由：能解决那些 BFS 内存爆掉的题。

2. 迭代加深展开了 19 万个节点，却比只展开 1.9 万个的 BFS 还快。 因为它的每个节点极其便宜（就是几次交换）， 而 BFS 每个节点都要往哈希表里插一个字符串。 节点数不等于时间 —— 还要看每个节点有多贵。

3. IDA* 只用 149 个节点。 一个好的估价函数，比任何常数优化都值钱。

为什么这一章没有「同题对比」组件

因为八数码规模太小 —— 四种方法都在几十毫秒内跑完， 进程启动的时间比算法本身还长，测出来的数字全是噪音。

所以这一章改用 count.cpp 在程序内部计时和计数。 这本身也是个值得学的做法：当被测对象比测量误差还小的时候， 就要把测量搬到程序内部去。

6单步看「一个大圆 vs 两个小圆」

八数码画不出来（状态是九个数字的排列），所以这个动画换成迷宫 —— 道理一模一样。

单向 vs 双向：一个大圆，还是两个小圆
单向访问 62 格　双向访问 47 格
第 1 / 20 步
0起
0终
蓝 = 从起点铺开的，橙 = 从终点铺开的，绿 = 两边撞上的那一格。灰色是墙。
换一张迷宫（1 = 能走，0 = 墙）
已访问格子数
2
扩了几圈
0
这张图上：单向要访问 62 格，双向只要 47 格。 迷宫小的时候差别不大，但格子数是按「半径的平方」涨的 —— 图一大，这个差距就是指数级的。
双向 BFS：起点和终点同时开始铺，谁的队列小就先扩谁。
  • 单向：从起点铺开一个圆，一直铺到终点。访问的格子 ≈ 半径 d 的圆面积。
  • 双向：起点和终点各铺一个小圆，在中间撞上。访问的格子 ≈ 两个半径 d/2 的圆。

上面那行状态栏实时显示两种模式各自访问了多少格。 迷宫小的时候差别不大，但格子数是按「半径的平方」涨的 —— 图一大，这个差距就出来了。（在状态图上是按「指数」涨，差距更夸张。）

把迷宫里的墙拆掉几堵（改成全 1），再对比一次 —— 空旷的图上双向的优势最明显。

7★ 对拍：四种方法互相验证

★ 正确的用法

把「IDA*」那一栏换成你自己写的（迭代加深或双向 BFS 都行），再点开始。

标准答案用的是第 15 章那份单向 BFS —— 和你要验的东西机制完全不同， 这才是有意义的交叉验证。

对拍器
生成器从目标状态倒着随机走 0~12 步（第 15 章那个套路），保证有解且不会太深。想验更深的局面，可以把生成器里的 12 改大 —— 但别超过 20，否则单向 BFS 那边会变慢。
// 八数码 —— IDA*（迭代加深 + 估价函数）
//
// 输入输出和前两份完全一样。
//
// ============ 只比 iddfs.cpp 多了一个函数 ============
//
// 迭代加深有个明显的浪费：明明离目标还差十万八千里，它还在傻乎乎地往下搜，
// 直到撞上深度上限才掉头。
//
// 如果能**估计**出「从现在这个局面出发，至少还要走多少步」，
// 就可以提前掐掉：
//
//     已经走了 g 步 + 至少还要 h 步 > 深度上限  →  这条路不可能在本轮走通，直接返回
//
// 这就是**估价函数**（第 16 章第 9 步提过的那个东西），也是 A* 家族的核心。
//
// ============ 这里用的估价：曼哈顿距离 ============
//
// 每个数字块「离它该在的位置」还差几格（横向差 + 纵向差），全部加起来。
//
// 为什么它是「至少还要走的步数」？
//   每走一步，只有一个数字块移动一格，它的曼哈顿距离最多减 1。
//   所以要把总距离降到 0，**至少**需要「总距离」那么多步。
//
// ⚠ 估价函数必须**不高估**（专业说法叫「可接纳」）。
//   一旦估多了，就可能把真正的最优解剪掉 —— 那就不是剪枝，是剪错了。
//   （回想第 16 章那句话：剪枝不该改变答案。）
//
// 效果：局面越深，IDA* 越占便宜。跑一下 count.cpp 看具体数字。


#include <bits/stdc++.h>
using namespace std;


const string GOAL = "123804765";
string cur;
int limitDepth;
int goalPos[256];                     // goalPos['5'] = '5' 在目标里的下标
const int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};


/** 曼哈顿距离之和：至少还要走这么多步 */
int h() {
    int s = 0;
    for (int p = 0; p < 9; p++) {
        char c = cur[p];
        if (c == '0') continue;       // 空格不算
        int q = goalPos[(int)c];
        s += abs(p / 3 - q / 3) + abs(p % 3 - q % 3);
    }
    return s;
}


bool dfs(int g, int prevMove) {
    int est = h();
    if (est == 0) return true;                  // 已经到目标
    if (g + est > limitDepth) return false;     // ★ 估价剪枝：本轮不可能走通


    int p = (int)cur.find('0'), i = p / 3, j = p % 3;
    for (int t = 0; t < 4; t++) {
        if (prevMove >= 0 && (t ^ 1) == prevMove) continue;
        int x = i + di[t], y = j + dj[t];
        if (x < 0 || x >= 3 || y < 0 || y >= 3) continue;


        swap(cur[p], cur[x * 3 + y]);
        if (dfs(g + 1, t)) return true;
        swap(cur[p], cur[x * 3 + y]);
    }
    return false;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    if (!(cin >> cur)) return 0;
    if (cur.size() != 9) { cout << -1 << "\n"; return 0; }


    for (int p = 0; p < 9; p++) goalPos[(int)GOAL[p]] = p;


    // 起手的深度上限直接从 h() 开始 —— 比它小的层数根本不可能有解
    for (limitDepth = h(); limitDepth <= 40; limitDepth++)
        if (dfs(0, -1)) { cout << limitDepth << "\n"; return 0; }


    cout << -1 << "\n";
    return 0;
}
点一下即可编辑

值得故意写错的：

  • 估价函数把空格也算进曼哈顿距离 → 高估了，会剪掉最优解，答案偏大
  • if (g + h() > limit) 写成 >= → 把恰好等于上限的解也剪了，答案偏大
  • 迭代加深忘了「不走回头路」 → 答案还是对的，但慢好几倍
  • 双向 BFS 不是整层扩，而是一次弹一个节点 → 可能得到非最短的答案
  • 双向 BFS 相遇时只算一边的步数 → 答案差一半

8阶段 3 小结：搜索的工具箱

★ 拿到一道搜索题，怎么选
情况 用什么
求「能不能到 / 有多少种方案 / 所有方案」 DFS（第 13 章）
求「最少多少步」，状态数不大 BFS（第 14、15 章）
求「最少多少步」，状态数大到内存装不下 迭代加深（本章）
同上，而且能想出一个不高估的估价函数 IDA*（本章）
求「最少多少步」，起点终点都明确、深度大 双向 BFS（本章）
状态会重复出现，且只关心结果不关心路径 记忆化搜索（第 17 章）
搜索树太大 剪枝（第 16 章）—— 这条和上面所有情况都能叠加

这七行就是阶段 3 的全部。 剩下的都是往里面填「什么是状态」「什么是一步」。

9自测

自测清单0 / 10
配套练习
这一章我卡在哪（过一个月回来看，这几行比整章正文都值钱）
阶段 3 到此结束

六章走完，你手上有：DFS、BFS、多源与状态图、剪枝、记忆化、迭代加深与双向搜索。

这是信息学竞赛里最能靠「想清楚」拿分的一块。 遇到不会做的题，写个搜索加几个剪枝，往往就能拿到一半以上的分。

接下来是阶段 4（贪心）—— 那一块最难的从来不是写代码，是证明它为什么对。 而第 9 章的二分答案里，你其实已经证过一次贪心了（「多装绝不吃亏」）。