search - A*算法中的星号是什么意思？

Question

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

我说得对吗？我未能成功寻找有关该主题的任何信息，但找不到任何引用资料。希望这个社区中最有经验的用户比我更了解 A* 的历史。

顺便说一句，我认为其他基于 A* 的算法(例如 IDA*、D*、SMA*、MOA*、NAMOA*...)遵循相同的名称约定。

Answer 1

原因是科学家首先提出了 Dijkstra 算法的改进版本，他们称之为 A1。后来，A*的发明者发现了A1的改进，他们称之为A2。然后，这些人设法证明，在所使用的启发式的某些假设下，A2 实际上是最优的。由于 A2 是最优的，因此更名为 A*。在科学中，特别是在优化中，“*”符号通常用于表示最优解。有些人还将“*”解释为“任何版本号”，因为事实证明不可能构建优于 A2/A* 的“A3”算法。

顺便说一句，在这种情况下，“最佳”并不意味着它达到最佳解决方案，而是在探索最小数量的节点的同时达到最佳解决方案。当然，A*也是完整的，这意味着它达到了最优解(如果我们使用可接受的启发式)。