<p>IDA* 是将启发式评估函数 f(n) = g(n) + h(n) 作为迭代加深的阈值限制，而非按深度限制；它用 f 值上限替代 max_depth，确保每轮聚焦最优估计路径，兼顾最优性与 O(d) 空间效率。</p>
ID A* 不是“结合”迭代加深和启发评估，而是把启发式评估函数 f(n) = g(n) + h(n) 直接嵌进迭代加深的框架里——每次迭代的深度限制，换成了 f 值上限。
为什么不能直接用 max_depth 做限制
普通迭代加深（IDS）按层数限制搜索深度，比如先搜深度 ≤ 1，再 ≤ 2……但对路径代价不均等的问题（如移动步数不同、边权非 1），深度浅 ≠ 代价小。八数码中一步移动可能让 h(n) 下降很多，也可能几乎没变；单纯卡“走了几步”，会漏掉真正有希望的分支，或者在无效深支上反复浪费时间。
IDA* 把这个“深度”替换成 f(n)：只允许进入 f(n) ≤ threshold 的节点。这样既保留了 DFS 的 O(d) 空间（d 是最大递归深度），又让每轮搜索都聚焦在当前最优估计路径附近。
-
threshold初始设为f(start) - DFS 过程中一旦遇到
f(n) > threshold，立即回溯，不往下走 - 记录所有越界
f(n)中的最小值，作为下一轮threshold - 只要
h(n)可采纳（h(n) ≤ h*(n)），就能保证首次到达目标时的解是最优的
h(n) 怎么选直接影响剪枝效率
选错启发式，IDA* 退化成慢速 DFS；选得好，能跳过 90% 以上无效状态。以八数码为例：
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 用
misplaced_count（错位棋子数）：计算快，但太弱，h(n)常远小于实际剩余步数，导致threshold上涨缓慢，迭代轮次多 - 用
manhattan_distance（曼哈顿距离和）：每个棋子到目标位置的行列差绝对值之和，可采纳且更紧，大幅减少迭代次数 - 绝不能用欧氏距离：在网格移动中不可采纳（比如斜向距离 1.41，但实际至少要 2 步），会破坏最优性保证
- 实际编码时，
h(n)必须是O(1)或O(n)计算，否则每次节点评估开销压倒剪枝收益
递归 DFS 主体里怎么写 f 剪枝
核心就一行判断：在进入子节点前，先算它的 f 值，超阈值就跳过。不是等进了再检查——那样已经多占栈帧、多算了一次 h。
bool ida_star(Node& node, int g, int threshold, int& next_threshold) {
int f = g + heuristic(node);
if (f > threshold) {
next_threshold = min(next_threshold, f); // 记录下界
return false;
}
if (is_goal(node)) return true;
<pre class='brush:php;toolbar:false;'>for (Node child : expand(node)) {
if (ida_star(child, g + 1, threshold, next_threshold))
return true;
}
return false;}
- 注意
g + 1：这里假设所有边权为 1；若边权可变，要传入真实代价g + cost(node → child) -
next_threshold必须用引用传入并持续更新，不能每次迭代重置为INT_MAX后再找 min——那样会漏掉上层已发现的更小越界值 - 没有显式 visited 集合，靠
f剪枝和 DFS 路径天然避免循环；但若图中存在零权环，仍需额外判重
容易忽略的边界与性能陷阱
很多人调通逻辑后一跑就 TLE 或 MLE，问题常出在这些地方：
-
heuristic()函数没做缓存：对同一状态反复计算h(n)，尤其在深递归中爆炸式重复 - 状态表示太重：比如用
vector<vector<int>>存八数码，每次复制构造开销大；应转成int（康托展开）或uint64_t（位压缩） - 没预处理静态信息：例如铁盘整理题中，相邻差值变化规律可提前算好，避免每次 expand 时遍历整个排列
-
threshold更新逻辑错：下一轮threshold必须严格大于本轮最小越界值，否则陷入死循环；常见错误是写成threshold = next_threshold却忘了清空next_threshold初始值
真正难的不是写对算法骨架，而是让 heuristic 足够紧、状态操作足够轻、剪枝触发足够早——这三者卡得准，IDA* 才从“理论上省空间”变成“实际上秒出解”。
