0

我正在尝试创建一个本地搜索启发式来解决 TSP，这个过程似乎失败了。我生成了一个随机哈密顿循环并将其存储在传出 [] 中，传出 [i] 表示源自 i 的边之一指向的顶点。distances[a][b] 表示从顶点 a 到顶点 b 的距离。但是，每当我运行此代码时，算法并没有优化我传入传出的哈密顿循环，而是简单地创建新循环 0->numcities-2->1->numcities-1。如果它可以提高顶点到其输出顶点的距离，它应该简单地重复切换输出顶点。我可能忽略了一些小事，但我根本无法弄清楚我做错了什么。顺便说一句，我将运行多次，这就是布尔值更改的用途。

for(int i = 0; i < numcities; i++)
{
   for(int j = i+1; j < numcities; j++)
   {
      if(distances[i][outgoing[i]] + distances[j][outgoing[j]] > distances[i][outgoing[j]] + distances[j][outgoing[i]] && i != outgoing[j] && j != outgoing[i])
      {
        changed = true;
        int temp = outgoing[j];
        outgoing[j] = outgoing[i];
        outgoing[i] = temp;
      }
    }
}
4

1 回答 1

1

问题是，当您交换outgoing[i]和时outgoing[j]，您正在创建两个子巡回 - 两个较小的循环。

例如，假设numcities=6您的出发行程是 0 1 2 3 4 5。假设您的if陈述对于 , 是正确i=1的j=3。您的代码集outgoing[1] = 4和outgoing[3] = 2. 所以代码认为巡演现在是 0 1 4 5 since outgoing[1] = 4。这并不完全是您所获得的巡回演出，但我认为这是相同的基本理念。

要解决此问题，您需要将游览分为 3 个部分 - (A) 直到并包括 cityi的部分，(B)i和j(包括j) 之间的部分，以及 (C) 之后的部分j。当您交换边缘时，您需要重新配置游览，因此 (A) 与以前相同，然后部分 (B) 反转，然后部分 (C) 完好无损。

所以在我的例子中，部分 (A) 是 0 1，部分 (B) 是 2 3，部分 (C) 是 4 5。在打破边缘 1-2 和 3-4 并重新连接后，您将获得游览 0 1 3 2 4 5。

您在此处实施的称为2-opt。你会在很多地方找到更多关于它的信息。

于 2015-04-27T00:02:12.530 回答