比 A* 更好的启发式
我注册了斯坦福大学的 ai-class.com，并在第一周的讲座中刚刚学习了 a* 算法以及如何比其他搜索算法更好地使用它。
我还展示了我的一位同学在 4x4 滑块拼图上实现它，他已将其发布于：http: //george.mitsuoka.org/StanfordAI/slidingBlocks/ 虽然我非常欣赏并感谢 George 实现了 A* 并发布了结果供我们娱乐。
我（和他）想知道是否有任何方法可以使过程更加优化，或者是否有更好的启发式 A*，例如比“不合适的块数”或“距离总和”的最大值更好的启发式函数达到目标”，这会加速事情的进展？ 另外，如果对于此类问题有比 A* 更好的算法，我也想了解它们。
感谢您的帮助，如果出现差异，在降级我的个人资料之前，请允许我有机会升级我的方法，或者即使要求删除问题，因为我仍在学习 stackoverflow 的方法。
I am enrolled in Stanford's ai-class.com and have just learned in my first week of lecture about a* algorithm and how it's better used then other search algo.
I also show one of my class mate implement it on 4x4 sliding block puzzle which he has published at: http://george.mitsuoka.org/StanfordAI/slidingBlocks/
While i very much appreciate and thank George to implement A* and publishing the result for our amusement.
I (and he also) were wondering if there is any way to make the process more optimized or if there is a better heuristic A*, like better heuristic function than the max of "number of blocks out of place" or "sum of distances to goals" that would speed things up?
and Also if there is a better algo then A* for such problems, i would like to know about them as well.
Thanks for the help and in case of discrepancies, before down grading my profile please allow me a chance to upgrade my approach or even if req to delete the question, as am still learning the ways of stackoverflow.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这取决于您的启发式函数。例如，如果您有一个完美的启发式 [
h*]，那么 贪婪< /a> 算法（*），将产生比 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* 运行双向搜索：从开始端，您可以使用启发式运行 A*，并从目标端运行常规 BFS。它会更快地得到解决方案吗？不知道，您可能应该对两种可能性进行基准测试并找出哪个更好。然而，用这个算法找到的解决方案也将是最优的，就像 BFS 和 A* 一样。
It depends on your heuristic function. for example, if you have a perfect heuristic [
h*], then a greedy algorithm(*), will yield better result then A*, and will still be optimal [since your heuristic is perfect!]. It will develop only the nodes needed for the solution. Unfortunately, it is seldom the case that you have a perfect heuristic.(*)greedy algorithm: always develop the node with the lowest
hvalue.However, if your heuristic is very bad:
h=0, then A* is actually a BFS! And A* in this case will developO(B^d)nodes, where B is the branch factor and d is the number of steps required for solving.In this case, since you have a single target function, a bi-directional search (*) will be more efficient, since it needs to develop only
O(2*B^(d/2))=O(B^(d/2))nodes, which is much less then what A* will develop.bi directional search: (*)run BFS from the target and from the start nodes, each iteration is one step from each side, the algorithm ends when there is a common vertex in both fronts.
For the average case, if you have a heuristic which is not perfect, but not completely terrbile, A* will probably perform better then both solutions.
Possible optimization for average case: You also can run bi-directional search with A*: from the start side, you can run A* with your heuristic, and a regular BFS from the target side. Will it get a solution faster? no idea, you should probably benchmark the two possibilities and find which is better. However, the solution found with this algorithm will also be optimal, like BFS and A*.
正如您在视频中了解到的，A* 的性能基于预期成本启发式的质量。让您的预期成本启发式尽可能接近该状态的实际成本将减少需要扩展的状态总数。还有许多变体在某些情况下表现更好，例如当在大状态空间搜索中面临硬件限制时。
The performance of A* is based on the quality of the expected cost heuristic, as you learned in the videos. Getting your expected cost heuristic to match as closely as possible to the actual cost from that state will reduce the total number of states that need to be expanded. There are also a number of variations that perform better under certain circumstances, like for instance when faced with hardware restrictions in large state space searching.