我相当确定A*算法中的* (星号)表示该算法是可接受的，即如果存在最短路径，它保证能在图中找到（当所使用的启发式方法是乐观的）。

我说的对吗？我一直在寻找关于这个话题的信息，但没有找到任何参考资料。希望社区中更有经验的用户能知道一些我不知道的关于A*历史的信息。

顺便说一下，我认为其他基于A*的算法，如IDA*、D*、SMA*、MOA*、NAMOA*等，也遵循相同的命名惯例。

回答：

原因是科学家们首先提出了Dijkstra算法的改进版本，称为A1。后来，A*的发明者发现了A1的改进版本，他们称之为A2。这些人随后证明了在某些关于所使用启发式的假设下，A2实际上是最优的。因为A2是最优的，所以它被重新命名为A*。在科学中，特别是在优化领域，” * “符号通常用来表示最优解。有些人还将” * “解释为“任何版本号”，因为已经证明不可能构建一个能超越A2/A*的“A3”算法。

顺便说一下，在这个语境中，“最优”并不意味着它达到了最优解，而是指它在探索最少数量的节点时达到了最优解。当然，A*也是完整的，这意味着它能达到最优解（如果我们使用可接受的启发式方法）。