c++ - 3D配置空间中的星型算法

Question

我对 A* 算法和其他基于图的算法进行了一些研究，但大多数教程和实现都是使用 2D 网格和 2 个参数(x、y 坐标)制作的。

有人在不同的配置空间中提供带有示例(C++ 或 Java)的好的教程或有关 A* 的链接吗？例如 3D 环境或非网格，具有 x、y、z 坐标或 x、y、方向或任何其他...

谢谢

Answer 1

一般的 A* 算法不包括网格和维度。它是加权图的最短路径算法。该图的节点和边是什么，完全是特定于场景的。

在二维网格的情况下，节点是网格单元，边缘指定邻接关系。可以从 3D 网格构建类似的图形。如果您不想将自己局限于网格，您可以构建具有任意连通性的任何图形。

节点不一定需要对应位置，权重也不一定需要对应距离。例如，Pinocchio System使用 A* 生成骨架嵌入。这里的距离是嵌入质量/能量(尽管能量不是沿着路径累积的)。节点对应于部分嵌入。