algorithm - 比 A* 更好的启发式

Question

我注册了斯坦福大学的 ai-class.com，并且刚刚在第一周的讲座中学习了有关 a* 算法的知识，以及如何更好地使用它而不是其他搜索算法。

我还展示了我的一位同学在 4x4 slider 拼图上实现它，他发表在:http://george.mitsuoka.org/StanfordAI/slidingBlocks/虽然我非常感谢并感谢 George 实现 A* 并发布结果供我们娱乐。

我(和他也)想知道是否有任何方法可以使过程更优化，或者是否有更好的启发式 A*，比如比“不合适的 block 数”的最大值更好的启发式函数或“到目标的距离总和”会加快速度？而且如果有比 A* 更好的算法来解决此类问题，我也想知道它们。

感谢您的帮助，如果出现差异，在对我的个人资料进行降级之前，请允许我有机会升级我的方法，或者即使要求删除问题，因为我仍在学习 stackoverflow 的方法。

Answer 1

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

但是，如果您的启发式非常糟糕:h=0，那么 A* 实际上是 BFS !而本例中的 A* 将开发 O(B^d) 个节点，其中 B 是分支因子，d 是求解所需的步骤数。
在这种情况下，因为你有一个单一的目标函数，一个bi-directional search (*) 会更有效率，因为它只需要开发 O(2*B^(d/2))=O(B^(d/2)) 节点，这要少得多那么A*会发展成什么。
双向搜索:(*)从目标节点和起始节点运行BFS，每次迭代从每一边开始一步，当两边都有一个公共(public)顶点时算法结束。

对于一般情况，如果您有一个不完美但不完全糟糕的启发式算法，A* 可能会比这两种解决方案表现得更好。

针对一般情况的可能优化:您还可以使用 A* 运行双向搜索:从开始端，您可以使用启发式运行 A*，并从目标端运行常规 BFS .它会更快地得到解决方案吗？不知道，您应该对这两种可能性进行基准测试，然后找出哪个更好。但是，用这种算法找到的解也将是最优的，就像 BFS 和 A* 一样。