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

我十分肯定的* （星）在A *算法意味着该算法是受理，即可以保证它发现在如果此路径存在图中的最短路径（当所采用的启发式是乐观的）。A *算法中的星号是什么意思？

我说得对不对？我没有找到有关该主题的任何信息，但我找不到任何参考。希望这个社区的大多数有经验的用户知道A *的历史与我的不同。顺便说一句，我认为像IDA *，D *，SMA *，MOA *，NAMOA *，等基于A *的其他算法遵循相同的名称约定。

来源

2016-03-05 FrankS101

不符合[维基百科]（https://en.wikipedia.org/wiki/A*_search_algorithm#History）。 – beaker

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

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

来源

2016-03-07 15:49:14 francoisr

我也从维基百科读到这个条目：https：//en.wikipedia.org/wiki/A*_search_algorithm。我特别寻找这个名称约定的参考（在一篇研究论文或着名的资料来源中）。 – FrankS101

挖了一下，我发现这个帖子可能会让你感兴趣：http://stackoverflow.com/a/29470434/2174693 – francoisr

谢谢。我看到我的问题是那个问题的重复。有趣的是，接受的答案是引用一篇已发表的论文。那篇论文的作者引用了维基百科在他们的文章中介绍该段落。那么谁首先在维基百科上写下这些内容？也许是哈特，也许是那篇论文之前的作者，谁知道...... – FrankS101

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

回答

相关问题