CodeVS/1174
2015年8月4日 (二) 00:19云璟月（讨论 | 贡献）的版本

(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

A*算法

我们把一切类似问题抽象成一个最短路问题：记 $D_AB$ 为在一个图中A、B两点间的最短路，求两点S、T的 $D_{ST}$ 。

类似于搜索，我们把已经搜索过的点集合记作P。接下来我们要搜一点A，将它加入P中，那么我们当然希望A一定在ST的最短路上，于是：

$D_{ST}=D_{SA}+D_{AT}$

记作： $F(A)=G(A)+H(A)$

其中，如果G，H都是已知量，那么直接找满足F(A)最小的A即可。然而实际情况是G已知，那么我们通过估计出一个H*(A)得到：

$F^*(A)=G(A)+H^*(A)$

那么F*(A)越小，A属于最短路的可能性越大，就把它加入P中，继续扩展点，直到T点也在集合P中，就得到答案了。这就是A*算法。

假设我们找到一种神奇的H*(A)=H(A)，那么无疑F*(A)就是最优解。

当 $H^*(A)<H(A)$ 时，我们就会搜索到更多的无效解，然而最后的P集合一定包含最优路径，A*算法一定有最优解。

当 $H^*(A)>H(A)$ 时，我们可能会在没有搜索到最优解的时候就错误的结束，A*算法保证能找到可行解，但不一定是最优解。

当 $H^*A=0$ 时，我们会搜索所有解，退化成bfs。

当 $F^*(A)=XA(X\inP)$ 时，这是Dijkstra算法。

$|H(x) - H^*(x)| = O(\log H^*(x))$ ===关于IDA*===通过控制G(A)进行迭代加深搜索，与迭代加深的深度优先搜索类似。可以避免判重等的时间、空间复杂度（代码也好写），但是在大数据量的时候不如普通的A*。==参考资料和扩展阅读==https://en.wikipedia.org/wiki/A*_search_algorithmhttp://m.blog.csdn.net/blog/CreationAugust/41929843