優化蠻力TSP解決方案

Question

我正在研究解決TSP的小型項目，但遇到問題。這個想法是通過簡單地找到最佳組合來優化非最優路徑的局部部分。這是通過一個簡單的遞歸排列生成函數完成的。

我現在想要做的是檢查當前的解決方案是否有任何潛在的改進（邏輯：如果解決方案的權重比當前更好，則不要調用置換函數）。

我遇到的問題是，當前的實現確實改進了解決方案，但並未達到最佳效果（我將結果與簡單的蠻力搜索進行了比較）。如果你指出我的邏輯缺陷或錯誤，我將不勝感激。 M - 是成本矩陣。幫助 - 當前的解決方案，最好的 - 最好的解決方案（類變量）

void City::Generate(int** M, int* help, int k, int &auxcost, int* best) { 
     int cost2 = 0; // текущая цена 
     if (k == range){ 
      for (int i = 0; i < range - 1; i++) 
       cost2 += M[help[i]][help[i + 1]]; 

      if (cost2 < auxcost){ 
       auxcost = cost2; 
       memcpy(best, help,range *sizeof(int)); 
       changed = true; 
      } 
     } 
     else{ 
      for (int j2 = k; j2<range; j2++){ 
       swap(help[k], help[j2]); 

       for (int i = 0; i < range - 1; i++) 
        tcost += M[help[i]][help[i + 1]]; 


       if (tcost <= auxcost) 
        Generate(M, help, k + 1, start, end, auxcost, best); 
        swap(help[k], help[j2]); 
      } 
     } 
    } 

Answer 1

據我所看到的，你的錯誤是在計算tcost削減遞歸。
您已經爲每個城市help[0]..help[k]更正了一個地方。但是，您計算tcost

for (int i = 0; i < range - 1; i++) 
    tcost += M[help[i]][help[i + 1]]; 

的全排列，就像你已經固定所有城市！實際上，遞歸函數可以改進當前置換的help[k+1]..help[range-1]部分的排列，從而提供比auxcost更優的答案。

相反，您應該只評估您正在計劃更改的部分排列組合而不是。如果繼續遞歸，則help[0], help[1], ..., help[k]的值不會更改。因此，如果值x，以這種方式計算的：

int x = 0; 
for (int i = 0; i < k; i++) // notice the difference in exit condition 
    x += M[help[i]][help[i + 1]]; 

大於auxcost大，則遞歸的這個分支不會找到最優解肯定。