CodeVS/1174

A*算法

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

类似于搜索，我们把已经搜索过的点集合记作P。接下来我们要搜一点A（A与P中一点有连边），将它加入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属于最短路的可能性越大。就满足条件的最小F*(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)=Len_{XA}$ (点 $X{\in}P$ ，XA有连边， $Len_{XA}$ 指的XA之间的边长)时，这是Dijkstra算法。

$|H(x)-H^*(x)|=O({\log}H^*(x))$

通过控制G(A)进行迭代加深搜索，与迭代加深的深度优先搜索类似。可以避免判重等的时间、空间复杂度（代码也好写），但是在大数据量的时候不如普通的A*。