algorithm - AO*算法如何实现？

Question

我注意到在实现搜索算法时会使用一些数据结构。比如我们用queue来实现BFS，用stack来实现DFS，用min-heap来实现A*算法。在这些情况下，我们不需要显式构造搜索树。

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

Answer 1

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

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

Can anybody provide me an efficient implementation?

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