java - 旅行推销员本地搜索启发式

Question

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

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;
      }
    }
}

Answer 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，因为 outgoing[1] = 4。这并不完全是您所得到的游览，但我认为这是相同的基本想法。

要解决此问题，您需要将游览分为 3 个部分 - (A) 直到并包括城市 i 的部分，(B) i 之间的部分code>和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。您可以在很多地方找到更多相关信息。