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

Question

我想知道如何在三维空间中使用Prim算法。把它放到上下文中：我想计算所有可能的和最短/最有效的方法来在墙上铺设电缆，并考虑3d空间中的一些不可用点/约束。

任何想法如何建模（算法以及技术上）？我知道常用的最短路径和最小/最大生成树算法，但直到现在才在2d空间中学习/使用它们。

Answer 1

您应该简单地将您的3D墙转换为图形。比方说，我们的墙是一个简单的立方体，我们把它分成许多小方块：

对于每一个路口，你在你的图表以及您在创建新的边缘交叉点之间每行创建一个新的顶点您图形。

既然你最终得到一个正则图，你可以使用Prim的算法。

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