隨機生成TSP解決方案的算法

Question

解決TSP問題（特別是Kernighan-Lin啓發式算法）的最常見啓發式算法需要在隨機生成的巡迴工作中進行工作，並改進從中開始的解決方案。但是，我想出的唯一方法是生成頂點的隨機置換，並檢查它是否爲解。

對於該問題的大型實例（例如1000個頂點），此過程可能需要一段時間。是否有另一種智能方式來更快速地生成TSP問題的隨機遊？請注意，我正在尋找一次巡視，不管成本如何，也不是最佳解決方案。

在此先感謝

Answer 1

您可以創建一個數組，其中包含問題的城市，然後隨機洗牌該數組（有一些方法可以做到這一點）。 結果數組實際上是一個隨機排列。

Answer 2

如果你只是尋找任何遊覽，您可以使用廣度或深度優先搜索，同時標誌着走訪節點產生的路徑。

Answer 3

您想使用空間填充曲線。