有人实施过SMA*搜索算法吗？

Question

我发现AIMA(人工智能:现代方法)中的算法描述根本不正确."必要"是什么意思？内存限制是多少？队列大小或处理过的节点？如果当前节点根本没有孩子怎么办？

我想知道这个算法本身是否正确.因为我搜索了互联网,但还没有人实现它.

谢谢.

Answer 1

我相信这个 PDF是 AIMA 的 SMA* 部分，适合那些没有这本书的人。

我首先注意到维基百科的伪代码在该行中有一个相当明显的错误：

parent.successors.remove(parent);

它应该是

parent.successors.remove(badNode);

（父母怎么能成为自己的继承人呢？）

“必要”是什么意思？

如果它的父级尚未在队列中，那么我们必须将其添加到队列中。否则，我们最终将再次搜索该节点。

内存限制是多少？队列大小或处理的节点？

队列将占用所有可用内存。已处理节点没有队列。这正是 SMA* 可以重新遍历节点并可能陷入困境的原因。

如果当前节点根本没有子节点怎么办？

如果一个节点没有子节点，那么它就是叶节点。如果它是叶节点，那么它就是终端节点。在这种情况下，如果它不是目标节点，我们将其 f 成本设置为无穷大，并将该信息传播到其父节点。