多次訪問的TSP

Question

您可以爲以下問題建議可能的方法：通過圖頂點查找路徑，以便兩個頂點出現次數之間的距離（邊權重總和）不會超過Di。它顯然是無限的，所以我想要爲這條路徑設置一個生成器。

Answer 1

當您的圖形滿足三角不等式時，christofides算法保證您在最佳值的2/3內。