A*搜索的时间复杂度是多少

Question

我是堆栈溢出的新手，但我来这里是因为我到处搜索，除了 wiki 之外，似乎找不到关于 A* 时间复杂度的太多信息。我还想将它与 Dijkstra 的算法进行比较，看看在 A* 中添加启发式算法如何提高它的性能。

我知道这是一个非常高级的话题，但我无法从 wiki 上给出的信息中完全理解它（即使对 wiki 上的 Dijkstra 算法的分析似乎也很先进）。

如果有人能更详细地解释时间复杂度，或建议有关该主题的任何阅读/学习材料，我将不胜感激。我确实对 A* 算法有很好的理解，但我现在才刚刚开始学习它的分析。

Answer 1

答案很简单，这取决于。星星本身并不是完整的算法。星星是具有启发式的 Dijkstra，它满足某些属性（如三角不等式）。您可以选择导致不同时间复杂度的不同启发式函数。最简单的启发式方法是直线距离。然而，还有更高级的东西，例如地标启发式。

在最坏的情况下，您总是需要探索整个社区，因此从一般分析角度来看，您不会比Dijkstra更好。然而，在大多数实际应用中，您可以获得更好的界限。只有当您知道图形和启发式函数的某些属性时才会这样做。然后，您可以做出一些导致更好复杂性的假设，但仅限于这些情况。

例如，如果您知道直线距离始终是图形中的正确距离，并且您使用直线距离启发式，那么您的A 星将具有最佳的复杂度Theta(1)。然而，对于大多数应用程序来说，这是一个非常强的假设。但是你可以想到这是怎么回事。

底线是：它极大地取决于您的图形结构和您的启发式函数。

互联网上也有很多，该算法非常受欢迎，因为它很容易实现，并且对于大多数情况已经足够快（例如，非复杂游戏）。