UCS算法迭代

Question

我一直在尝试实施 UCS，为此我认为最好先手绘出它的工作原理草图，而不是通过代码。我有一个图表

我尝试在上图中实现 UCS（统一成本搜索）。但是当我有

时，我在状态中感到困惑

打开节点为：(V2,9),(V5,9),(V5,10),(V2,12),(V6,13)

封闭节点为：(V1,0),(V3,4),(V4,5),(V2,6)

我是否必须将 (V2,9) 包含在开放节点中，因为 (V2,6) 已经在封闭节点中？.

我试着看不同的文章，每篇都给了我不同的答案。有人说包括它，而其他人说不包括。

Answer 1

这取决于你的优先队列是如何实现的。基本上有两个选择：

(1) 一个节点不能在队列中出现超过一次。访问一个节点时，如果您发现到队列中已存在的相邻节点的路径较短，则根据新找到的路径（如果更短）更新其优先级。

在这种情况下，队列条目 (V2,9) 在访问节点 V3 后已经被 (V2,6) 替换。 (V2,12) 永远不会被添加到队列中，因为在访问 V4 时 V2 已经以更高的优先级存在于队列中。

(2) 您不强制队列中节点的唯一性。从队列中获取条目时，您检查该节点是否已被访问（=它在您所谓的封闭节点中），并在这种情况下跳过它。

在这种情况下，队列包含条目 (V2,9),(V5,9),(V5,10),(V2,12),(V6,13) （如您在问题中所述）。您跳过 V2，因为它已经被访问过并访问 V5。

无论如何，一个节点在被访问后永远不会被添加到队列中，否则算法不会停止。