2-Opt本地搜索實現

Question

我想實現本地搜索（與2-opt）來解決旅行商問題。但是，我無法正確重新創建一個完整的電路（節點巡視）。我認爲我的算法可能有缺陷。這是我的實現2-OPT的：

A-> B - > ... D->ç - > ...一個

切換到

A-> D- > ... B->ç - > ...一個

我的一般過程看起來像一個標準的交換： 商店b作爲臨時 器C作爲TEMP2 A-> d B-> C^

我的代碼如下所示：

node* twoOpt(double** distance_matrix, node* tour, int NUM_CITIES) 
{ 
int rand1, rand2; 
int temp, temp2; 

rand1 = rand() % NUM_CITIES; //a 
rand2 = rand() % NUM_CITIES; //d 

do 
{ 
    //Ensure the two numbers are different 
    while (rand1 == rand2 || tour[rand1].destination == rand2 || rand1 == tour[rand2].destination) 
     rand2 = rand() % NUM_CITIES; 

    //Make swap 
    temp = tour[rand1].destination; //b 
    temp2 = tour[rand2].destination; //c 

    tour[rand1].destination = rand2; 
    tour[rand1].distance = distance_matrix[rand1][rand2]; //a->d 

    tour[temp].destination = temp2; 
    tour[temp].distance = distance_matrix[temp][temp2]; //b->c 

} while(!travelTour(tour, NUM_CITIES)); 

return tour; 
} 

現在我明白了這個代碼是不完美的。例如，如果兩個節點重新洗牌不會創建完整的電路，則代碼只會在第二個節點再次嘗試之前更改第二個節點。但是我的問題只是爲什麼我無法在第一時間完成全部巡演。

感謝您的幫助！

Answer 1

我終於找到了問題。我的解決方案概念不完整。我不僅需要指出a-> d和b-> c，還需要將新巡演中受影響的一半的所有內容都倒過來。換句話說，我必須反轉從b到d的舊路徑。正確的代碼如下：

do 
{ 
    //Ensure the two numbers are different 
    while (rand1 == rand2 || tour[rand1].destination == rand2 || rand1 == tour[rand2].destination) 
     rand2 = rand() % NUM_CITIES; 

    //Make swap 
    temp = tour[rand1].destination; //b 
    temp2 = tour[rand2].destination; //c 

    tour[rand1].destination = rand2; 
    tour[rand1].distance = distance_matrix[rand1][rand2]; //a->d 

    oldNode = temp; 
    currNode = tour[oldNode].destination; 

    tour[temp].destination = temp2; 
    tour[temp].distance = distance_matrix[temp][temp2]; //b->c 

    //Swap directions of graph for d->b 
    while (currNode != temp2) 
    { 
     nextNode = tour[currNode].destination; 
     tour[currNode].destination = oldNode; 
     oldNode = currNode; 
     currNode = nextNode; 
    } 
} while(!travelTour(tour, NUM_CITIES)); 

它仍然不完全漂亮。如果我不得不重新啓動項目，我不會根據節點存儲數據。我會以邊緣的形式存儲它們，每條邊都知道它的兩個節點。這將使交換更容易。但是，這是我的解決方案。

Answer 2

你需要鏈修正：

從Drools Planner manual。