核心逻辑与数学原理
在高维状态空间中，普通广度优先搜索（BFS）会因状态爆炸导致内存崩溃，而深度优先搜索（DFS）则容易在没有最优解的深层分支中盲目死磕。
状态空间 是指从初始状态出发，通过所有合法的操作（如走一步棋、向左转），能够到达的所有可能状态的集合。
维度 指的是描述一个状态所需要的独立变量（特征）的数量
高维状态空间 当一个问题的状态需要极多的变量来描述，或者每次状态转移都有极多的选择（即分支系数大）。
迭代加深搜索（Iterative Deepening DFS, IDS）： 其核心思想是将 DFS 的空间优势与 BFS 的步数最优性相结合。通过显式限制搜索深度上限 max_dep，从 1 开始逐步递增。若在当前深度限制下未找到解，则废弃整棵搜索树，将 max_dep + 1 重新开始 DFS。对于分支系数为 k 的搜索树，第 m 层的节点数为 k^m。尽管 IDS 重复搜索了前 m-1 层，其总时间复杂度仍为：
$$T(m)=\frac{k(k^m-1)}{k-1}\approx k^m$$
首项 $a_1 = k$，公比 $q = k$，项数为 $m$。 根据等比数列求和公式 $S_m = \frac{a_1(1-q^m)}{1-q}$
$T(m) = k^1 + k^2 + \dots + k^m$。 当 $k=10$ 时： $T(m) = 10^1 + 10^2 + \dots + 10^m$。 $10^m$ 比之前所有项之和还要大。 从渐进复杂度的角度来看，常数项和低阶项被忽略，主导项即为 $k^m$。
这与直接执行 BFS 的时间复杂度同阶，空间复杂度从$O(k^m)$降为 $O(m)$。
双向广度优先搜索（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}})$。从几何角度看，它将一个大半径的高维球体膨胀，转化为两个小半径球体对位拦截，在空间与时间上实现了数量级的优化。
这里的“球体”，是指以起始节点为圆心，在状态空间中向外等距离扩散的层级结构。
状态设计与算法推导
1. IDS 状态设计与剪枝推导
定义函数 bool dfs(int cur, int dep, int max_dep)。
- cur：当前状态。
- dep：当前搜索深度。
- max_dep：当前迭代限定的最大深度。
- 乐观估计剪枝：设计估价函数 h(cur)，表示当前状态到达目标的理论最小步数。若满足 dep + h(cur) > max_dep，说明在当前深度限制下绝无可能产生解，立即回溯。这是 IDS 升级为 IDA* 的数学核心。
2. Bi-BFS 空间与相遇对位推导
使用两个队列 q_start 和 q_end，以及哈希表 vis_start 和 vis_end 维护两端扩展出的步数。
- 空间对位优化法则：每次扩展时，选择当前队列规模较小的一侧进行单层扩展。设正向队列大小为 $V_1$，逆向队列大小为 $V_2$。若 $V_1\ll V_2$，扩展 $V_1$ 带来的新状态增量为 $k\times V_1$。优先扩展较小队列能强制让搜索树在高维空间中向狭窄的瓶颈靠拢，避免某一侧盲目膨胀。
- 相遇判定逻辑漏洞修复：在双向 BFS 中，为了保证首次相遇即为最短路径，在采用“优先扩展较小队列”优化时，必须确保每次扩展完整的单层（即当前队列中的所有节点）。若在单层扩展中发现新状态 next 已被对侧访问，总步数即为两侧步数之和。
模板
IDA*
// h(u) 为估价函数，需根据具体题目定义
bool dfs(int u, int dep, int max_dep) {
if (dep + h(u) > max_dep) return false; // 乐观估计剪枝：当前深度+预估距离超出限制
if (h(u) == 0) return true; // h(u)==0 表示已到达目标状态
for (int v : get_next(u)) { // 枚举所有可能的后继状态
if (dfs(v, dep + 1, max_dep)) return true; // 递归搜索，找到解则返回
}
return false;
}
void solve() {
int max_dep = h(start); // 从理论最小深度开始迭代
while (!dfs(start, 0, max_dep)) { // 若当前深度无解，增加深度限制
max_dep++;
}
// 输出 max_dep 即为最优步数
}双向BFS
// q[0]为起点队列，q[1]为终点队列；vis记录从两端出发到达某点的距离
queue<int> q[2];
int vis[MAXN][2];
int bfs() {
q[0].push(start); vis[start][0] = 0;
q[1].push(end); vis[end][1] = 0;
while (!q[0].empty() && !q[1].empty()) {
// 动态选择规模较小的一侧扩展，平衡搜索空间
int d = (q[0].size() <= q[1].size()) ? 0 : 1;
int sz = q[d].size();
while (sz--) {
int u = q[d].front(); q[d].pop();
for (int v : get_next(u, d)) { // d=0为正向边，d=1为反向边
if (vis[v][d] != -1) continue;
if (vis[v][1 - d] != -1) return vis[u][d] + 1 + vis[v][1 - d]; // 两端相遇
vis[v][d] = vis[u][d] + 1;
q[d].push(v);
}
}
}
return -1; // 无法连通
}
核心逻辑：选择规模较小的队列，把这一层所有节点全部处理完
NOIP 实战避坑指南
- Bi-BFS 逆向转移算错算漏：双向 BFS 的终点逆向扩展时，状态转移必须是正向转移的逆元。如果图是有向图，逆向 BFS 必须跑在反向图上。若直接套用正向转移函数，两路搜索将在高维空间中平行错过，导致队列打满爆内存或死循环。
- IDS 忘记重置全局标记：在编写迭代加深（IDS）时，每一轮 max_dep 增加后，本质上是重新开一棵 DFS 树，必须清理上一轮遗留的全局 vis 标记或全局最优解变量。否则第二轮搜索刚进第一层就会被上一轮残存的标记错误剪枝，返回无解。
经典真题与核心解法代码
1. 洛谷 P2326 移动玩具
- 题意描述：在一个 4x4 的黑白棋盘上，有 8 个黑子和 8 个白子。给定初始状态和目标状态，每次可以将一个棋子移动到相邻的空位上，求最少步数。
- 问题本质：状态空间图的无权最短路。
- 核心解题思路：4x4 棋盘状态可用一个 int 二进制位压缩存储（共 16 位，1 标识黑，0 标识白）。利用双向 BFS 进行双端对位拦截。
#include <queue>
#include <cstring>
#include <algorithm>
int vis[65536][2]; // 0表示正向，1表示逆向
int bfs_double(int start, int target) {
if (start == target) return 0;
std::queue<int> q[2];
std::memset(vis, -1, sizeof(vis));
q[0].push(start); vis[start][0] = 0;
q[1].push(target); vis[target][1] = 0;
// 定义16宫格相邻的位移变换矩阵
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
while (!q[0].empty() && !q[1].empty()) {
int dir = q[0].size() <= q[1].size() ? 0 : 1;
int sz = q[dir].size();
while (sz--) {
int u = q[dir].front();
q[dir].pop();
for (int i = 0; i < 16; ++i) {
int x = i / 4, y = i % 4;
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
int j = nx * 4 + ny;
// 提取第i位和第j位的值
int bit_i = (u >> i) & 1;
int bit_j = (u >> j) & 1;
if (bit_i == bit_j) continue; // 颜色相同无需交换
// 交换第i位和第j位，得到新状态
int next_state = u ^ (1 << i) ^ (1 << j);
if (vis[next_state][dir] != -1) continue;
if (vis[next_state][1 - dir] != -1) {
return vis[u][dir] + 1 + vis[next_state][1 - dir];
}
vis[next_state][dir] = vis[u][dir] + 1;
q[dir].push(next_state);
}
}
}
}
}
return -1;
}
2. 洛谷 P1074 靶形数独
- 题意描述：在标准九宫格数独规则基础上，每个格子根据所在圈数有不同的分值权重。给出残缺数独，求最高总分。
- 问题本质：深层组合搜索的路径优化与精确覆盖。
- 核心解题思路：利用位运算记录行、列、九宫格的可用数字状态。为最小化分支系数，采用搜索顺序对位优化，优先从已知数字最多（即空格最少）的行开始搜索，瞬时拦截无用状态。
#include <algorithm>
int row[9], col[9], cell[3][3], score_map[9][9];
int blank_count[9], row_order[9];
int ans = -1;
int grid[9][9];
// lowbit 提取二进制中最右侧的 1
inline int lowbit(int x) { return x & -x; }
void dfs(int r_idx, int c, int current_score) {
if (r_idx == 9) {
ans = std::max(ans, current_score);
return;
}
int r = row_order[r_idx];
if (c == 9) {
dfs(r_idx + 1, 0, current_score);
return;
}
if (grid[r][c] != 0) {
dfs(r_idx, c + 1, current_score + grid[r][c] * score_map[r][c]);
return;
}
// 掩码 0x1FF 对应 9 个 1 (表示 1-9 都可用)
// 找出当前行列宫均未使用的数字交集
int available = ~(row[r] | col[c] | cell[r / 3][c / 3]) & 0x1FF;
while (available) {
int p = lowbit(available);
available ^= p; // 抹除该位
// __builtin_ctz 计算末尾 0 的个数，刚好映射回填入的数字 (0~8)
int num = __builtin_ctz(p) + 1;
row[r] |= p; col[c] |= p; cell[r / 3][c / 3] |= p;
dfs(r_idx, c + 1, current_score + num * score_map[r][c]);
row[r] ^= p; col[c] ^= p; cell[r / 3][c / 3] ^= p; // 回溯
}
}
void solve() {
// 根据每行空格数量从小到大排序行索引，大幅减少搜索树分支
for (int i = 0; i < 9; ++i) row_order[i] = i;
std::sort(row_order, row_order + 9, [](int a, int b) {
return blank_count[a] < blank_count[b];
});
dfs(0, 0, 0);
}