2-Opt本地搜索实现

我想实现本地搜索（与2-opt）来解决旅行商问题。但是，我无法正确重新创建一个完整的电路（节点巡视）。我认为我的算法可能有缺陷。这是我的实现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; 
}

现在我明白了这个代码是不完美的。例如，如果两个节点重新洗牌不会创建完整的电路，则代码只会在第二个节点再次尝试之前更改第二个节点。但是我的问题只是为什么我无法在第一时间完成全部巡演。

感谢您的帮助！

来源

2012-10-12 Jojo Jonas

我终于找到了问题。我的解决方案概念不完整。我不仅需要指出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));

它仍然不完全漂亮。如果我不得不重新启动项目，我不会根据节点存储数据。我会以边缘的形式存储它们，每条边都知道它的两个节点。这将使交换更容易。但是，这是我的解决方案。

来源

2012-10-16 15:52:52