algorithm - 如何在3d空间中使用Prims算法

Question

我想知道如何在 3d 空间中使用 Prim 的算法。将其放入上下文中:我想计算所有可能和最短/最有效的方法来在墙上铺设电缆，同时考虑 3d 空间中的一些不可用点/约束。

关于如何建模(算法和技术)的任何想法？我确实知道常见的最短路径和最小/最大生成树算法，但直到现在才在二维空间中学习/使用它们。

Answer 1

您只需将 3D 墙转换为图形即可。假设我们的墙是一个简单的立方体，我们将它分成许多小立方体:

对于图形中的每个交点，您都会创建一个新顶点，对于交点之间的每条线，您都会在图形中创建一条新边。

由于您最终得到的是规则图，因此可以使用 Prim 算法。

如果您想要更高的粒度，您可以省略障碍物所在的顶点和边，并减小立方体的大小。