c - 2-Opt 本地搜索实现

Question

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

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

切换到

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

我的一般过程看起来像标准交换：将 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 手册。