c - 2-Opt 本地搜索实现

Question

我正在尝试实现本地搜索(使用 2-opt)来解决旅行商问题。但是，我无法正确地重新创建完整的电路(节点之旅)。我认为我的算法可能有缺陷。这是我对 2-opt 的实现:

a->b->...d->c->...a

切换到

a->d->...b->c->...a

我的一般过程看起来像一个标准的交换:将 b 存储为临时将 c 存储为 temp2a->db->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));

它仍然不是很漂亮。如果我必须重新启动项目，我不会按照节点存储我的数据。我会根据边存储它们，每条边都知道它的两个节点。这将使交换更容易。尽管如此，这是我针对此设计的解决方案。