Delaunay Triangulation對於無向圖的等效

Question

我正在研究等價於旅行商問題的路徑規劃算法。我不知道我可能有多少個節點，所以我願意犧牲速度的準確性。我的問題可以建模爲一個完全連通的圖，節點之間的轉換成本不僅僅是節點之間的距離。我想限制我的搜索空間到位於delaunay三角網上的連接（我讀過的研究指出，TSP解決方案中95-100％的連接位於delaunay三角網上），但是由於我的圖不能表達作爲二維甚至三維幾何，我不能直接在我的表現中使用它。是否有一種算法導致與適用於不符合幾何表示的圖形的Delaunay三角剖分相等的三角剖分（由於過度約束，不能將連接代價表示爲點之間的幾何距離）？

Answer 1

對於n維，您可以嘗試使用灰色代碼。