通過斷開連接線段的最短路徑

Question

我有一個接縫常見的問題，但沒有找到解決它的名稱或算法。

給出一組歐幾里德2d空間中的線段，我喜歡找到通過所有線段的最短路徑。

這個問題例如出現在繪圖機上，該繪圖機使用筆在紙上繪圖，並且必須最小化繪製事物之間無用的行進時間。

這個問題的名稱是什麼？有沒有簡單的近似解決方案？

Answer 1

最小化繪圖筆的非繪圖行程距離的問題非常接近traveling salesman problem，其中線段端點爲頂點並在繪製線段的兩端之間分配成本0。

與TSP不同，您的問題允許您在線段中間啓動和停止繪製線條。 power icon上的垂直線是您想要以兩個線段繪製線條而不是一次繪製線條的時間示例。不過，我猜想，只有當你開始繪畫的地方與你停止繪畫的地方不同時，纔會出現這種情況。如果我的猜測是正確的，那麼通過解決旅行銷售人員問題可以獲得的解決方案與最佳解決方案的區別僅在於圖表的寬度。

Answer 2

您必須爲此調整tsp的解決方案。

你可以通過遺傳算法做到這一點。它不能保證你會得到最好的解決方案，但你通常可以在很短的時間內接近它。

您基本上從一組隨機解決方案開始。然後，您對每個解決方案進行輕微隨機更改，然後測量行進距離。你保持距離最短的那些。重複這個過程直到新一代不提供優化或者你沒有時間。