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

Question

我想知道如何在三維空間中使用Prim算法。把它放到上下文中：我想計算所有可能的和最短/最有效的方法來在牆上鋪設電纜，並考慮3d空間中的一些不可用點/約束。

任何想法如何建模（算法以及技術上）？我知道常用的最短路徑和最小/最大生成樹算法，但直到現在纔在2d空間中學習/使用它們。

Answer 1

您應該簡單地將您的3D牆轉換爲圖形。比方說，我們的牆是一個簡單的立方體，我們把它分成許多小方塊：

對於每一個路口，你在你的圖表以及您在創建新的邊緣交叉點之間每行創建一個新的頂點您圖形。

既然你最終得到一個正則圖，你可以使用Prim的算法。

如果您想要更高的粒度，您可以忽略障礙物所在的頂點和邊緣，並減小立方體的大小。