algorithm - D* Lite 和 LPA* 算法 : concept of predecessors and successors

Question

我正在尝试实现 D* Lite和 LPA*算法(均由 Sven Koenig 提出)，我很难理解每个节点包含的前驱和后继列表的概念。我尝试在各种来源寻找答案，但找不到确定的答案。

谁能帮我解决一下？

谢谢。

Answer 1

在有向图上:

• 后继者是那些可以从当前节点到达的节点
• predecessors 是可以到达当前节点的那些节点。

在无向图上(常见于简单示例)，它们将是相同的。

在下面的(无向)4-连通格上

• 节点 E 的后继是 B、D、F 和 H(也就是说，如果您在 E，则可以到达箭头所指的任何状态)。
• 节点 E 的前任是 B、D、F 和 H(通过翻转箭头的方向并查看到达 E 的内容来找到)。