以最短距離覆蓋圓中所有點的最佳算法

找到覆蓋圓中最小距離的所有點的路徑的最佳算法。從（0,0）開始，不需要返回（0,0），不像TSP以最短距離覆蓋圓中所有點的最佳算法

看起來像一些任務？ – Miller

建議您在math.stackexchange.com上發佈此信息？你有選擇或要求的編程語言嗎？ – robnick

「最佳算法」在哪？你到目前爲止嘗試過什麼？ –

您可以使用動態編程。它使用所有組合來檢查所有AZ距離。然後你可以檢查最短的AZ路線。我在gebweb tsp solver的javascript中找到了一個工作示例。

2014-02-06 12:31:21 Bytemain

夥計，蠻力解決方案需要n！時間 –

對不起。我的意思是AZ路線是所有組合。 – Bytemain

如果不需要返回，那麼它不是一個循環/循環，而是一條路徑。

通過圖中所有頂點的路徑稱爲哈密爾頓路徑，您所描述的問題是「最小權重哈密爾頓路徑」，它與TSP一樣硬。所以你不會找到比任何可用的TSP算法更好的算法（但你可以使用已知的TSP算法進行小的調整來解決這個問題，例如動態規劃和分支和界限）。

2014-02-06 12:37:26

不是*循環*一個圓圈。在二維空間中，這意味着沒有兩條線相互交叉。（我認爲）。如果我是正確的，那麼TSP可能更容易出現問題，並且可能是多項式求解的。 – amit

阿米特，我認爲多項式解決方案不可能 –

我想你的意思是遍歷一個圓內的所有點（夫妻x，y），並可以選擇包含或排除圓（等高線）。我在這裏回顧這些定義。 CIRCLE：與點C（中心）的距離爲R> 0的平面上的點。DISK：與中心的距離爲< = R> 0的平面的點。從這種意義上講，您希望移動所有點的DISK。

有很多方法可以「觸摸」一個圓圈內的所有點（不是圓的所有點，這是另一個問題）。我認爲「最好」意味着：不要重複一個觀點並且走最短的路線。

如果這是問題，我可以建議啓發式算法。

2014-02-06 13:43:29 AngMas

回答