学了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。