把 14.3 节"深度限制、反复加深"的思路，用在 14.4 节的 f 值上——用 DFS 的低内存，换来和 A* 一样的方向感。
14.4 节的 A* 有了"方向感"，能少走很多冤枉路，但它用优先队列保存所有待探索的节点——这一点和 BFS 一样，队列（这里是优先队列）在最坏情况下要同时装下和搜索前沿一样多的节点，内存开销是 O(前沿大小)。当搜索空间巨大（比如经典的十五数码问题，状态数是天文数字）时，A* 一样会遇到内存爆炸的问题。
14.3 节已经展示过一次同样的解决思路：IDDFS 用"深度限制 + 反复加深"，把 BFS 的 O(b^d) 内存压到了 DFS 的 O(深度)。IDA*（Iterative Deepening A*）把这个思路原封不动地搬过来，只是把限制的对象从"深度"换成了 A* 里的 f(n) = g(n) + h(n)。
IDA* 做的事情和 IDDFS 几乎一样：跑一次带限制的 DFS，如果没找到解，就放宽限制，重新跑一次。区别只有一处：
| IDDFS（14.3 节） | IDA*（本节） | |
|---|---|---|
| 限制的对象 | 深度（整数，从 0 开始） | f(n) = g(n) + h(n)（可能是任意数值） |
| 剪枝条件 | depth == limit 就停止往下 | f(n) > limit 就停止往下 |
| 下一轮的新限制 | 直接 limit + 1 | 本轮所有被剪掉的节点里，最小的那个 f 值 |
f 值可能是任意的数（取决于边权和启发式函数），如果本轮限制是 4，被剪掉的节点里最小的 f 值是 7，那么把限制改成 5 或 6 完全是浪费——中间根本不存在任何节点的 f 落在 (4,7) 之间，这两轮注定还是白跑。IDA* 每轮结束后，直接把新限制设成"本轮被剪掉的节点里最小的 f 值"，跳过所有注定失败的中间尝试，这是 IDA* 和 IDDFS 最关键的不同之处。用一棵带边权、带启发值的小树演示：S 是起点，G 是目标；每个节点旁边标出 g（从 S 走到这里的实际代价）、h（启发式估计）、f = g+h：
G 挂在 A 下面。第 1 轮，limit = h(S) = 4：S（f=4，展开）→ A（f=8>4，剪枝，记录 8）→ B（f=4，展开）→ C（f=4，展开，是死路）→ D（f=7>4，剪枝，记录 7）。本轮被剪掉的节点中最小的 f 是 min(8,7)=7，新限制设为 7（如果只是"+1"，会先浪费两轮去尝试 5 和 6，那两个值根本不存在任何节点）。
第 2 轮，limit = 7：S（f=4，展开）→ A（f=8>7，仍然剪枝，记录 8）→ B（f=4，展开）→ C（死路）→ D（f=7≤7，展开，但 D 也是死路）。本轮被剪掉的节点只有 A，新限制设为 8。
第 3 轮，limit = 8：S（f=4，展开）→ A（f=8≤8，展开）→ G（f=7≤8，检查是目标，找到！）。答案就是 g(G) = 7。
| 1 | const int FOUND = -1, INF = 0x3f3f3f3f; |
| 2 | int ansG; // 找到目标时，记录下它的 g 值（最终答案） |
| 3 | |
| 4 | // 返回 FOUND 表示找到目标；否则返回"这棵子树里，超过 limit 的最小 f 值" |
| 5 | int DFS(int u, int g, int limit) |
| 6 | { |
| 7 | int f = g + H(u); |
| 8 | if (f > limit) return f; // ★ 超过限制，剪枝；把这个 f 值带回去，供下一轮参考 |
| 9 | if (IsGoal(u)) { ansG = g; return FOUND; } |
| 10 | |
| 11 | int minExceed = INF; |
| 12 | for (auto [v, w] : adj[u]) // v：邻居节点，w：这条边的代价 |
| 13 | { |
| 14 | int t = DFS(v, g + w, limit); |
| 15 | if (t == FOUND) return FOUND; // 子树里找到了，一路返回 FOUND |
| 16 | minExceed = min(minExceed, t); // 记录这棵子树里"最小的超限 f 值" |
| 17 | } |
| 18 | return minExceed; |
| 19 | } |
| 20 | |
| 21 | int IDAStar(int start) |
| 22 | { |
| 23 | int limit = H(start); // 第一轮的限制，就是起点的启发值（g=0） |
| 24 | while (true) |
| 25 | { |
| 26 | int t = DFS(start, 0, limit); |
| 27 | if (t == FOUND) return ansG; |
| 28 | if (t == INF) return -1; // 没有任何节点被剪枝，说明搜索空间已经穷尽，无解 |
| 29 | limit = t; // ★ 直接跳到"本轮被剪掉的最小 f 值"，而不是 +1 |
| 30 | } |
| 31 | } |
+1，而是取"这一轮里所有被剪枝的节点中最小的 f 值"（第 16 行 minExceed 就是为了收集这个信息）。IDA* 和 A* 找到的答案完全一样（只要 h 不高估），区别只在于用什么资源去换取效率：
| 对比项 | A*（14.4 节） | IDA*（本节） |
|---|---|---|
| 需要的额外数据结构 | 优先队列，保存整个搜索前沿 | 不需要，只是普通的 DFS 递归栈 |
| 内存占用 | O(前沿大小)，可能很大 | O(深度)，非常小 |
| 时间开销 | 每个节点只访问一次 | 浅层节点会在多轮之间被重复访问（和 IDDFS 同理，通常代价不大） |
| 适合场景 | 内存足够、搜索空间不算特别巨大 | 搜索空间极大（如十五数码），内存是主要瓶颈 |
limit++，虽然结果依然正确，但会导致大量"中间限制"轮次完全找不到任何新节点、白白浪费整轮的搜索时间，尤其当边权跨度较大时问题更明显。h 高估，可能把通向真正最优解的分支提前剪掉，导致算出的答案不是最短路。DFS 函数里容易被忽略，尤其是从简单的树形例子（如本节演示）直接搬到实际的图上时。