algorithm - D* Lite 和 LPA* 算法：前任和后继的概念

Question

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

谁能帮我解决这个问题？

谢谢你。

Answer 1

在有向图上：

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

在无向图（简单示例中很常见）上，它们将是相同的。

在下面的（无向）4-连通格上

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