我已经读过，在将 A* 应用于问题时，如果您的启发式是一致的，那么您可以进一步优化 A* 搜索。Boost Graph Library 提供了两个版本的 A* 算法：astar_search和astar_search_tree. 文档对两者之间的区别不是很清楚；其中之一是否执行假设一致启发式的优化搜索？
问问题
875 次
2 回答
5
通过查阅 Boost 邮件列表，我得到了我正在寻找的答案。我将在这里为后代重现答案：
区别在于是否应该努力避免多次访问同一个顶点。对于通常可以使用许多路径到达顶点的图，您应该更喜欢 astar_search 以避免重新访问该顶点及其后续节点的额外工作。如果同一顶点不太可能出现在多条路径上，或者检查顶点的成本足够低以至于不值得避免重复工作，请使用不记得之前访问过哪些顶点的 astar_search_tree。尝试查找重复顶点的缺点是它需要越来越多的内存来存储以前见过的顶点的查找表，并且搜索和更新该表需要时间。两个版本的算法都需要允许的启发式才能正常工作。
于 2013-04-30T21:16:13.017 回答
-1
_tree和非_treeboost 图算法版本之间的区别在于，该_tree版本假定您的图实际上是一棵树，因此它没有循环，并且只有一个箭头表示节点。
于 2013-04-24T20:12:43.803 回答