如何实现AO*算法？

Question

我注意到在实现搜索算法时会使用一些数据结构.例如,我们使用队列来实现BFS,堆栈实现DFS和min-heap来实现A*算法.在这些情况下,我们不需要显式构建搜索树.

但我找不到一个简单的数据结构来模拟AO*算法的搜索过程.我想知道显式构建搜索树是否是实现AO*算法的唯一方法？任何人都可以为我提供有效的实施吗？我非常感谢你的帮助.

Answer 1

免责声明：我还没有实现 AO*，因此我可能是错的。

实现 AO* 应该与 A* 没有什么不同。您使用堆，但每个成员应该是节点向量（一个或多个节点），而不是只有一个节点。在某种程度上，这取决于如何为您提供（与或）规则，但填充堆应该非常容易。所以第一个问题的答案是否定的，没有必要显式地构造树，因为您不需要为 A* 这样做。请记住，堆实际上是搜索树的表示，因此有人可能会说您在遍历树时实际上是在构建树。关于

有人能为我提供有效的实施吗？

您需要通过提供至少一些伪代码，甚至更好的一段代码来显示您如何解决该问题，以显示出一些努力。然后我们可以提出如何通过改进数据结构来提高效率的建议。