查看CodeVS/1174的源代码 ←CodeVS/1174

==A*算法==
===A*能解决的问题简化===
我们把一切类似问题抽象成一个最短路问题：记<m>D_{AB}</m>为在一个图中A、B两点间的最短路，求两点S、T的<m>D_{ST}</m>。
===A*算法===
类似于搜索，我们把已经搜索过的点集合记作P。接下来我们要搜一点A（A与P中一点有连边），将它加入P中，那么我们当然希望A一定在ST的最短路上，于是：
::::<m>D_{ST}=D_{SA}+D_{AT}</m>
::::记作：<m>F(A)=G(A)+H(A)</m>
其中，如果G，H都是已知量，那么直接找满足F(A)最小的A即可。然而实际情况是G已知，那么我们通过估计出一个H*(A)得到：
::::<m>F^*(A)=G(A)+H^*(A)</m>
那么F*(A)越小，A属于最短路的可能性越大。就满足条件的最小F*(A)把它加入P中（可以用堆处理），继续扩展点，直到T点也在集合P中，就得到答案了。这就是A*算法。
===关于H*(A)的分析===
假设我们找到一种神奇的H*(A)=H(A)，那么无疑F*(A)就是最优解。

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

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

当<m>H^*(A)=0</m>时，我们会搜索所有解，退化成bfs。

当<m>F^*(A)=Len_{XA}</m>(点<m>X{\in}P</m>，XA有连边，<m>Len_{XA}</m>指的XA之间的边长)时，这是Dijkstra算法。
===时间复杂度===
<m>|H(x)-H^*(x)|=O({\log}H^*(x))</m>
===关于IDA*===
通过控制G(A)进行迭代加深搜索，与迭代加深的深度优先搜索类似。可以避免判重等的时间、空间复杂度（代码也好写），但是在大数据量的时候不如普通的A*。
==参考资料和扩展阅读==
https://en.wikipedia.org/wiki/A*_search_algorithm
http://m.blog.csdn.net/blog/CreationAugust/41929843

[[分类:启发式搜索]]