A*搜索算法

A*（读作“A 星”）是一种在网络中寻找最短路线的更聪明的办法——这个网络可以是地图栅格、道路图，或是电子游戏关卡里的方格。它的做法，是给迪杰斯特拉算法那种耐心的搜索加上一种“方向感”。普通的迪杰斯特拉算法会像池塘里的波纹一样朝各个方向同等地向外探索，完全不知道目标在哪里。A* 在每一步都会多问一句：从这里到目标大约还有多远？有了这个提示，它就会把搜索向目标方向倾斜，而不是把力气浪费在背离目标的乱走上，因此通常能快得多地到达目标，同时仍然找到一条真正最短的路径。

对于每一个它要考虑的位置，A* 都会权衡两个数字。第一个是从起点走到这里已经实际花掉的代价——这和迪杰斯特拉算法记的账是一样的。第二个是一个估计值，叫做启发值，表示从这里到目标还剩多少代价；在栅格上，这往往就用直线距离或“横平竖直”的街区距离来算，很容易得出。A* 把这两个数加在一起，每次总是优先展开总和最小的那个位置。于是它会偏向那些既容易到达、又看起来离目的地近的位置，自然而然地把搜索推向正确的方向。

需要注意的是，这个估计值绝不能高估真实的剩余距离——它必须保持乐观，永远不能声称目标比实际更远。只要启发值始终这样保持乐观（专业说法叫“可采纳的”），A* 就和迪杰斯特拉算法一样，必定返回一条最短路径，却用少得多的搜索量。事实上，如果你给 A* 一个永远猜成零的启发值，它就退化回了迪杰斯特拉算法——这也正是人们把 A* 形容为“迪杰斯特拉加上一个好提示”的原因。