比A*更好的启发式算法

Question

我正在参加斯坦福大学的ai-class.com课程，在第一周的讲座中学习了关于a*算法的知识，以及它如何比其他搜索算法更好地使用。

我还展示了我的一个同学在4x4滑块拼图上实现它的方式，他已经在http://george.mitsuoka.org/StanfordAI/slidingBlocks/上发布了结果。虽然我非常感激并感谢George实现A*并为我们的娱乐发布结果。

我和他都想知道是否有任何方法可以使这个过程更加优化，或者是否有比“错位块数”或“到目标距离之和”的最大值更好的启发式函数来加快速度？

如果有比A*更好的算法，也请告诉我。

感谢您的帮助，如果有不符，请在降低我的档案之前给我一个机会改进我的方法，甚至如果需要删除问题。因为我仍在学习stackoverflow的方法。

- Abhishek Sakhaparia

---

你尝试过寻找A*算法的替代方案吗？ - GolezTrol

我在提问之前按照您所说尝试了，但是没有令人满意的结果，其中一个是blobmap算法。因此，我认为在这里提问会是更好的方法。（顺便感谢GollezTrol的回复） - Abhishek Sakhaparia

Answer 1

这取决于你的启发函数。例如，如果你有一个完美的启发式函数[h*]，那么贪心算法(*)将比A*算法产生更好的结果，并且仍然是最优的[因为你的启发式函数是完美的！]。它只会开发出解决方案所需的节点。不幸的是，很少有完美的启发式函数。
(*)贪心算法：总是开发具有最低h值的节点。

然而，如果您的启发式非常糟糕：h=0，那么A*实际上就是BFS！在这种情况下，A*将开发O(B^d)个节点，其中B是分支因子，d是解决所需的步骤数。
在这种情况下，由于您只有一个目标函数，双向搜索 (*)将更有效，因为它只需要开发O(2*B^(d/2))=O(B^(d/2))个节点，比A*少得多。
双向搜索：(*)从目标和起始节点运行BFS，每次迭代从两侧各推进一步，当两个前沿都有共同顶点时算法结束。

对于平均情况，如果您的启发式不完美但也不是完全糟糕的话，A*可能会比这两种方法表现更好。

平均情况下的可能优化：您还可以使用A *运行双向搜索：从起始侧，您可以使用您的启发式和来自目标侧的常规BFS运行A *。它会更快地获得解决方案吗？没有头绪，您应该对这两种可能性进行基准测试并找出哪种更好。但是，使用此算法找到的解决方案也将是最优的，就像BFS和A *一样。

- amit

---

谢谢Amit的澄清。我已经修改了问题，并希望听听您的意见，是否采用的4x4拼图方法是合适的，或者还有很大的改进空间。 - Abhishek Sakhaparia

Answer 2

A* 的性能取决于预期成本启发式的质量，就像您在视频中学习的那样。使您的预期成本启发式与从该状态实际获得的成本尽可能匹配将减少需要扩展的状态总数。此外，还有一些特定情况下表现更佳的变体，例如在搜索大状态空间时面临硬件限制时。

- Nick Larsen