学了A怎么能补血IDA??
IDA*
前置芝士🧀
想吃芝士蛋糕惹QAQ
ID(迭代加深搜索)（from:OIwiki);
定义
迭代加深是一种 每次限制搜索深度 的 深度优先搜索;
解释
迭代加深搜索的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度 \(d\)，当\(d\) 达到设定的深度时就返回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度加一，重新从根开始。
既然是为了找最优解，为什么不用 \(BFS\) 呢？我们知道 \(BFS\) 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的 \(BFS\) 就显出了劣势。事实上，迭代加深就类似于用 \(DFS\) 方式实现的 \(BFS\)，它的空间复杂度相对较小。
当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 \(BFS\) 的。
过程
首先设定一个较小的深度作为全局变量，进行 \(DFS\)。每进入一次 \(DFS\)，将当前深度加一，当发现 \(d\) 大于设定的深度 \(limit\) 就返回。如果在搜索的途中发现了答案就可以回溯，同时在回溯的过程中可以记录路径。如果没有发现答案，就返回到函数入口，增加设定深度，继续搜索。
A*
请见上篇一闪一闪亮晶晶，满天都是A*
发现：
A*算法需要去维护一个优先队列来存储状态，有时会MLE，并且对堆进行一次操作需要花费\(O(\log N)\)的时间。不是很优，考虑优化。
IDA*
定义
（大雾）:
IDA* 算法其实是同时运用迭代加深与全局最优性剪枝。
即IDA* 是在DFS中 加入估价函数\(h\) 再考虑迭代加深。
原理及实现
观察A*中的\(f^*\)函数
- \(f^∗\)函数：从起点到当前点再到终点的估计距离。
即
（其函数定义与A* 相同）
使用DFS,若其函数值大于你的规定深度\(d\),就进行回溯操作。
规定深度\(d\)在DFS动态更新。初始规定深度\(d\)取为起点的总成本估计值\(h(s)\)。
在一次DFS中，每当因超过规定深度\(d\)而停止时，就记录所有尚未访问的后继结点的总成本估计的最小值。
DFS结束后，将规定深度\(d\)更新为这一最小值，继续下一轮DFS。