本篇简述一下IDA*算法，并列出代码帮助大家理解。
（1）算法简介
IDA*(ID A*)算法是一种启发式搜索算法，他是采取了迭代加深的 A*算法，使用了深度优先搜索的方式。
相对于A*算法，IDA*算法主要解决了：
1. A*算法需要判重，对优先级排序的问题。
2. A*算法使用堆，需要大量空间存储的问题。
（2）算法思想
IDA*算法的基本思想是设置一个搜索深度，这个搜索深度从0开始依次递增。使用深度优先搜索在这个深度内搜索目标，可以知道第一个找到目标的最小深度其实就是最短路径。
（3）回顾DFS
DFS是深度优先搜索，DFS的模板如下：
1 2 3 4 5 6 7 8 9 | void DFS(int u){ if(isTarget(u)){//如果u是目标 //记录u } for(int i=head[u];i;last[i]){//访问u的连接结点 int v=to[i]; DFS(v); }} |
（4）引入IDA*
因为IDA*基于迭代加深，所以需要一个函数来进行迭代加深。
1 2 3 4 5 6 7 8 | void incDeep(int u){ for(int i=0;;i++){//深度加强 if(IDAsstar(u,i)){ //输出解 break; } }} |
有了叠在加深之后，我们就可以写IDA*的核心代码了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | bool IDAstar(int u,int deep){ if(predict()>deep){//预测以最快的速度都得超过剩余深度才能达到终点 return false; } if(isTarget(u)){//如果u是目标 //记录u return true; } bool flag=false; if(deep>0){//还可以继续加深 for(int i=head[u];i;last[i]){//访问u的连接结点 int v=to[i]; flag=flag|IDAstar(v,deep-1);//只要有一个是true就行,所以用| } } return flag;} |
（5）优化
IDA*基于深度优先，本文距离采用递归实现，递归有深度限制，改成栈模拟递归将会更优。
（6）缺点
每轮搜索失败进行迭代加深后都需要重新开始搜索。
（7）应用
适用于A*算法无法满足某些特殊要求时的一种替代算法。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程