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

Question

我正在尝试创建一个本地搜索启发式来解决 TSP，但这个过程似乎失败了。我生成了一个随机哈密顿循环并将其存储在 outgoing[] 中，其中 outgoing[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;
      }
    }
}

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。所以代码认为自 outgoing[1] = 4 以来，游览现在是 0 1 4 5。这并不完全是您要进行的游览，但我认为这是相同的基本理念。

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

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

travelling salesman local search heuristic

java

debugging

traveling-salesman

hamiltonian-cycle