你會如何解決旅行商問題的這種變化？

Question

不得不這樣做的工作;我給出了一個近似的解決方案，因爲我無法弄清楚如何攻擊它。我知道這是NP難，但我很好奇，你將如何解決如下：

鑑於100點的位置和旅行商，位置劃分爲五組的20個地點。每天的行程將從同一個中心位置開始。儘量減少推銷員的總行程距離。

Answer 1

這裏有兩種可能的方法：

• 選擇一個Heuristic for the TSP，所以它需要訪問20個城市出100。然後刪除那些城市，從剩餘的選擇20修改，並重復，直到你選擇20箇中的20個。
• 使用啓發式將圖分成5個區域。使用像Held-Karp這樣的算法解決每個區域的TSP問題。如果你需要更好的解決方案，你可以在5個地區的邊界玩耍，每次重新運行Held-Karp。

請參閱Optimized TSP Algorithms爲Held-Karp算法。它在時間找到解決方案，因此它可用於大於20的輸入。