我在斯坦福大学的 ai-class.com 注册，并且刚刚在我第一周的讲座中学习了关于 a* 算法以及如何比其他搜索算法更好地使用它。
我还展示了我的一位同学在 4x4 滑块拼图上实现它，他发表在:http://george.mitsuoka.org/StanfordAI/slidingBlocks/
虽然我非常感谢并感谢 George 实现 A* 并发布结果供我们娱乐。
我(和他也)想知道是否有任何方法可以使过程更加优化，或者是否有更好的启发式 A*，例如比“错位块数”或“距离总和”的最大值更好的启发式函数到目标”这会加快速度吗？
而且，如果有更好的算法来解决此类问题，那么我也想了解它们。
感谢您的帮助，如果出现差异，在对我的个人资料进行评分之前，请让我有机会升级我的方法，或者即使 req 删除问题，因为我仍在学习 stackoverflow 的方法。
最佳答案
这取决于您的 heuristic function 。例如，如果您有一个完美的启发式 [ h* ]，那么 greedy 算法(*) 将产生比 A* 更好的结果，并且仍然是最佳的 [因为您的启发式是完美的!]。它将只开发解决方案所需的节点。不幸的是，您很少有完美的启发式方法。
(*)greedy 算法:始终开发具有最低 h 值的节点。
但是，如果您的启发式非常糟糕: h=0 ，那么 A* 实际上是 BFS !在这种情况下，A* 将开发 O(B^d) 节点，其中 B 是分支因子，d 是求解所需的步骤数。
在这种情况下，因为你有一个单一的目标函数，a bi-directional search (*) 会更有效，因为它只需要开发 O(2*B^(d/2))=O(B^(d/2)) 节点，这比 A* 开发的要少得多。
双向搜索:(*)从目标节点和起始节点开始运行BFS，每次迭代从每一边开始一步，当两边有一个公共(public)顶点时，算法结束。
对于一般情况，如果您的启发式不完美，但并非完全可怕，则 A* 可能会比两种解决方案都表现得更好。
平均情况的可能优化 :您还可以使用 A* 运行双向搜索:从开始端，您可以使用启发式运行 A*，并从目标端运行常规 BFS。它会更快地得到解决方案吗？不知道，您可能应该对两种可能性进行基准测试，然后找出哪个更好。但是，使用该算法找到的解决方案也将是最优的，例如 BFS 和 A*。
关于algorithm - 比 A* 更好的启发式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7828731/