高效状态空间搜索：迭代加深与双向广度优先算法的深度解析

核心逻辑与数学原理

在高维状态空间中，普通广度优先搜索（BFS）会因“状态爆炸”导致内存崩溃，而深度优先搜索（DFS）则容易在没有最优解的深层分支中“盲目死磕”。

• 迭代加深搜索（Iterative Deepening DFS, IDS）：其核心思想是将 DFS 的空间优势与 BFS 的步数最优性相结合。通过显式限制搜索深度上限 $max\text{dep}$，从 $1$ 开始逐步递增。若在当前深度限制下未找到解，则废弃整棵搜索树，将 $max\text{dep} + 1$ 重新开始 DFS。对于分支系数为 $k$ 的搜索树，第 $m$ 层的节点数为 $k^m$。尽管 IDS 重复搜索了前 $m-1$ 层，其总时间复杂度仍为：

$$\textstyle \text{总时间复杂度} = \frac{k(k^m - 1)}{k - 1} \text{ 近似为 } k^m$$

这与直接执行 BFS 的时间复杂度同阶，但其空间复杂度仅为 $O(m)$，从根本上解决了解空间过大导致的内存越界（MLE）问题。

• 双向广度优先搜索（Bidirectional BFS, Bi-BFS）：当搜索的起始状态与目标状态均已知时，从起点（正向）和终点（逆向）同时扩展状态。传统 BFS 拓展至深度 $d$ 的状态空间规模为 $O(k^d)$。而 Bi-BFS 双方各自拓展 $\frac{d}{2}$ 的深度并在中间相遇，状态空间规模缩减为 $O(2 \times k^{\frac{d}{2}}) = O(k^{\frac{d}{2}})$。从几何角度看，它将一个半径为 $d$ 的巨大高维球体膨胀，转化为了两个半径为 $\frac{d}{2}$ 的小球体膨胀，对位拦截，空间与时间实现了数量级的对位优化。

状态设计与算法推导

以经典图论路径/状态变换问题为例。设状态用整型或字符串表示，标准设计如下：

1. IDS 状态设计与剪枝推导

定义函数 bool dfs(int cur, int dep, int max_dep)。

• cur：当前状态。
• dep：当前搜索深度。
• max_dep：当前迭代限定的最大深度。
• 乐观估计剪枝（未来演判）：设计一个估价函数 $h(cur)$，表示当前状态到达目标的理论最小步数。若满足 $dep + h(cur) > max\text{dep}$，则说明在当前深度限制下绝无可能产生解，立即回溯。这一步推导是 IDS 升级为 IDA* 的数学核心。

2. Bi-BFS 空间与相遇对位推导

使用两个队列 Q_start 和 Q_end，以及两个哈希表或数组 vis_start 和 vis_end 维护两端扩展出的步数。

• 空间对位优化法则：每次扩展时，不应该机械地交替轮流扩展一步。必须选择当前队列规模（size）较小的那一侧进行单层扩展。数学推导：设正向队列大小为 $V_1$，逆向队列大小为 $V_2$。若 $V_1 \text{ 远小于 } V_2$，扩展 $V_1$ 带来的新状态增量为 $k \times V_1$；若扩展 $V_2$，增量为 $k \times V_2$。优先扩展较小队列能强制让搜索树在高维空间中向“狭窄的瓶颈”靠拢，避免某一侧盲目膨胀，从而最大化榨干空间性能。
• 相遇判定：若在一侧扩展新状态 next 时，发现 vis_other.count(next) 为真，则代表两军相遇。总最短步数即为 vis_curr[cur] + 1 + vis_other[next]。

C++ 标准源码

以下为双向广度优先搜索（Bi-BFS）的标准工程模板，融入了“动态选择较小队列”的空间对位优化技术。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>

// 演示用的状态转换：单次变换改变字符串中的一个字符
std::vector<std::string> get_next_states(const std::string& u) {
    std::vector<std::string> neighbors;
    for (size_t i = 0; i < u.length(); ++i) {
        std::string v = u;
        // 模拟某种状态变换规则（例如字符自增）
        if (v[i] < 'z') {
            v[i]++;
            neighbors.push_back(v);
        }
    }
    return neighbors;
}

int bidirectional_bfs(const std::string& start, const std::string& target) {
    if (start == target) return 0;

    std::queue<std::string> q_start, q_end;
    // vis 数组记录从起点/终点出发到达该状态的最短步数
    std::unordered_map<std::string, int> vis_start, vis_end;

    q_start.push(start);
    vis_start[start] = 0;

    q_end.push(target);
    vis_end[target] = 0;

    while (!q_start.empty() && !q_end.empty()) {
        // 核心空间对位优化：永远选择状态数较小的一侧进行扩展
        if (q_start.size() <= q_end.size()) {
            int sz = q_start.size();
            for (int i = 0; i < sz; ++i) {
                std::string u = q_start.front();
                q_start.pop();

                int cur_dist = vis_start[u];
                std::vector<std::string> neighbors = get_next_states(u);

                for (const auto& next_state : neighbors) {
                    if (vis_start.count(next_state)) continue; // 避免自环重复搜索

                    // 致命踩坑点：必须在入队时立刻检测是否相遇，若在出队时检测会多扩展一层无用状态
                    if (vis_end.count(next_state)) {
                        return cur_dist + 1 + vis_end[next_state];
                    }

                    vis_start[next_state] = cur_dist + 1;
                    q_start.push(next_state);
                }
            }
        } else {
            // 逆向扩展逻辑
            int sz = q_end.size();
            for (int i = 0; i < sz; ++i) {
                std::string u = q_end.front();
                q_end.pop();

                int cur_dist = vis_end[u];
                // 注意：在实际 NOIP 题目中，逆向变换的转移方程需满足自变量逆向对等性
                std::vector<std::string> neighbors = get_next_states(u); 

                for (const auto& next_state : neighbors) {
                    if (vis_end.count(next_state)) continue;

                    if (vis_start.count(next_state)) {
                        return cur_dist + 1 + vis_start[next_state];
                    }

                    vis_end[next_state] = cur_dist + 1;
                    q_end.push(next_state);
                }
            }
        }
    }
    return -1; // 状态不连通
}

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

    std::string start_str, target_str;
    if (std::cin >> start_str >> target_str) {
        std::cout << bidirectional_bfs(start_str, target_str) << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

1. Bi-BFS 逆向转移算错算漏 双向 BFS 的终点逆向扩展时，状态转移必须是正向转移的逆元。例如，正向操作是“将矩阵中 $A$ 位置的值赋给 $B$ 位置”，逆向操作绝对不是同样赋值，而是要把这个动作反过来。如果图是有向图，逆向 BFS 必须跑在反向图（Reverse Graph）上。若直接套用正向转移函数，两路搜索将在高维空间中平行错过，导致队列打满爆内存或死循环。
2. IDS 忘记重置全局标记 在编写迭代加深（IDS）时，每一轮 max_dep 增加后，由于本质上是重新开一棵 DFS 树，选手常常挂在“没有清理上一轮遗留的全局 vis 标记”或“全局最优解变量”。导致第二轮搜索时，刚进第一层就被上一轮残存的标记错误剪枝，返回无解，直接丢失整题分数。

经典 NOIP/洛谷 真题

1. 洛谷 P2326 移动玩具

• 题意描述：在一个 $4 \times 4$ 的黑白棋盘上，有 8 个黑子和 8 个白子。给定初始状态和目标状态，每次可以将一个棋子移动到相邻的空位上，求最少步数。
• 问题本质：十六数码状态空间的无权图最短路。
• 核心解题思路：
• 状态压缩：$4 \times 4$ 的二进制矩阵可用一个 int 存储。
• 空间对位：状态空间高达 $\binom{16}{8} = 12870$。采用双向 BFS，双方各自用哈希表或直接用大小为 $65536$ 的整型数组记录步数。每次挑两端队列中较小的一个进行单层状态转移，当碰头时输出答案。

2. 洛谷 P1074 靶形数独

• 题意描述：在标准九宫格数独规则基础上，每个格子根据所在圈数有不同的分值权重。现给出一个残缺的数独，求能获得的最高总分。
• 问题本质：深层组合搜索的路径优化。
• 核心解题思路：
• 迭代思维与位运算精简：此题常用 DFS 框架，但其核心优化策略与上下界及迭代加深的思想同气连枝。
• 搜索顺序对位：先统计每行每列已知数字的数量，优先从“空格最少”（即分支系数最小）的行开始进行深度搜索，每一步用位运算 $O(1)$ 提取可填状态，实现对高维无用状态空间的瞬时拦截。