algorithm - 如何在 Dijkstra 算法中找到邻居？

Question

我该如何寻找节点的邻居？是什么让某个节点成为另一个节点的邻居？顺便说一句，我正在用 Lua 编写代码

Answer 1

使用 A*，您可以定义三件事：

1. 从一个相邻节点移动到另一个节点的成本
2. 给定节点和目标节点之间的距离
3. 与任何给定节点相邻的节点

其中第一个可以是您想要的简单或复杂。当我在所有节点之间距离相同的情况下进行简单的基于网格的寻路时，我只是一直返回 1 以进行非常简单的查找。

Dijkstra 的算法实际上涵盖了其中的第二个，通常只返回 0。

但你的问题是关于第三件事：

如果您在网格上执行此操作，您可以找到作为您正在查看的网格空间的欧几里德邻居的网格空间。也就是说，对于网格空间 x2y2，其邻居是欧几里得空间中的 x1y2、x3y2、x2y1 和 x2y3。

如果您不处理网格，我怀疑您想要做的方式是在将它们放置在世界中或之后直接填充每个节点的兄弟数据，然后将其存储在关联的列表中与那个节点。您可以通过计算从一个节点到每个其他节点的距离并找到最短的节点或类似的东西来做到这一点。它可能非常昂贵，但你只会在一开始就做一次，所以如果这些节点不是动态的，应该没问题。