A*搜索算法
A*是一套步骤（一种算法），计算机可以用来计算如何在两个地方之间快速到达某地。如果你有一个地点的清单，以及从一个地方直接到达另一个地方有多难，使用A*可以迅速告诉你最快的方法。它与Dijkstra算法有关，但它会做出聪明的猜测，这样它就不会花那么长的时间去尝试缓慢的方法。如果你只想要两个地方之间的路径，这是一个很好的系列步骤。如果你要从同一张地图上寻找许多路径，那么有一些更快的方法，可以一次找到所有的答案，比如Floyd-Warshall算法。如果你想在一次旅行中访问几个地方（旅行推销员问题），A*就不起作用。
步骤
A*首先需要一个你能去的所有地方的清单，然后它需要一个每个地方之间有多远的路的清单。然后，它将告诉你从A地到Z地的最快方法。
举个例子，我们说A与B和C相连，B和C都与D和E相连，D和E都与Z相连，从A到Z有4种可能的途径，你可以走A-B-D-Z、A-C-D-Z、A-B-E-Z或A-C-E-Z。使用A*的计算机首先要看从A到B和从A到C有多难，这就是这些地方的 "成本"。一个地方的成本意味着从A到那个地方有多难。在写下这两个成本后，计算机看一下从B到D有多难，并将其加入B的成本。它把这写成了D的成本。然后计算机看一下从C到D有多难，并把它加到C的成本上。这是一个不同的D的成本，如果它比它已经拥有的成本低，它就会取代旧的。计算机只想知道最佳路径，所以它忽略了成本较高的路径。它只会记住A-B-D和A-C-D中的一个，以较快者为准。
最后，它从D到Z，找到一个成本，从E到Z，也找到一个成本。它得到了Z的最终成本，这是它能得到的最小的成本。现在计算机知道哪条路是最快的，而且它有了答案。计算机可以做一系列类似的步骤，但有很多很多的地方。每一次，它都会看一下离A最近的地方，然后把这个地方的邻居的费用加起来。
人们把上述一系列的步骤称为Dijkstra算法。Dijkstra算法可能很慢，因为它要看很多地方，而这些地方可能从Z出发走错了路。如果你问计算机如何从一个城市到附近的城市，Dijkstra算法可能最终会在另一个州寻找。
A*解决了这个问题。A*让你告诉计算机一个猜测，即从每个地方到终点有多远。计算机可以用这个猜测来告诉你从某地到Z地大概需要多远。它不会只选择离A地最近的地方看，而是看可能会有最低总费用的地方。它通过将成本与预期的剩余距离相加来找到这个总数。这样一来，它就可以只看事情可能会好转的方向。如果猜测不完美也没关系，但即使是一个简单的错误猜测，也能使程序的速度加快很多。如果你想在现实世界的两个地方之间找到一条路径，一个好的猜测只是它们之间的直线距离。真正的道路会更长，但这让程序猜到了，它就不会走错方向了。
在数学或计算机科学文献中，这种猜测往往是一个地方的函数，它被称为启发式。每个地方是一个顶点，两个地方之间的每个路径是一条边。这些都是来自图论的词汇。
