5

我很清楚旅行商问题的DP解决方案；也称为 TSP 的 Held 和 Karp 算法。

我已经用位掩码实现了它，它是这样的：

int TSP(int pos, int bitmask) {
  if (bitmask == (1<<(K+1))-1)
      return dist[pos][0];              // Completing the round trip

  if (memo[pos][bitmask] != -1)
      return memo[pos][bitmask];

  int answer = INF;
  for (int i = 0; i <= K; i++) {
      if (i != pos && (bitmask & (1 << i)) == 0)
          answer = Math.min(answer, dist[pos][i] + TSP(i, bitmask | (1 << i)));
  }

  return memo[pos][bitmask] = answer;     // Storing the best dist for the set of traveled cities and untraveled ones.

}

这个算法相当快；15个城市的计算速度比较快。但是，我注意到它可以进一步改进以适应大约 20 个城市。

1）如果dist矩阵是对称的，或许我们可以利用这个性质来防止重复计算。（例如 a->b->c->d->a == a->d->c->b->a）

2）同时使用上限和下限进行修剪。上述算法能够在很短的时间内得到它的第一个可能的最优解，也许可以使用它。

我已经尝试根据上述两个原则改进算法。但是，我没有得到更好的算法。

我是否在徒劳地尝试改进不可能的事情？你怎么看？

4

1 回答 1

1

我想你是对的。在你的方法下，城市的最大数量可能是20,21或22，但不能是25。这是因为你的算法中的状态数是n *（2 ^ n），当n = 20时，大约是10 ^7，当n=25时，大约是10^9，这是一个非常大的数字。使用现代计算机，它可以在 1 秒内处理大约 10^7 次计算。但是处理 10^9 的计算大约需要 100 秒。

所以我认为如果要处理更多的城市，一些近似算法可能有用，比如模拟退火算法、遗传算法等。或者你可以使用多台机器并缩小问题。

于 2013-10-29T06:47:33.983 回答