2.9　改进A*算法的内存占用：IDA*

IDA*是一个叫作迭代深化DFS（Iterative Deepening Depth-First Search）算法的变种，内存使用量比A*小，因为它不使用数据结构存储找到的和访问过的节点。

准备工作

学习本节之前，最好对递归原理有所了解。

操作步骤

本节较长，可以分成两大步骤：创建主函数和创建内部的递归函数。请注意代码中的注释，以便更好地理解代码逻辑：

1. 定义主函数GetPathIDAstar：

2. 声明并计算算法中要用到的变量：

3. 实现算法循环：

4. 构建递归的内部函数：

5. 做好开始递归的准备工作：

6. 对每个邻接点应用递归：

7. 返回递归结果的值：

运行原理

我们会发现，这个算法与递归版本的深度优先搜索相似，但是使用的是A*中的基于启发式算法制定决策的思想。主函数负责启动递归并构建结果路径，递归函数负责遍历图，查找目标节点。

延伸阅读

这次我们还要实现一个不同的BuildPath函数，你可能已经使用了之前定义的BuildPath。否则，我们还要实现这个还没有定义的方法：