java - 具有 Held 和 Karp 算法的旅行商

Question

我很清楚旅行商问题的 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) 同时使用上限和下限进行修剪。上述算法能够在很短的时间内得到第一个可能的最优解，也许可以用。

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

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

Answer 1

我认为你是对的。在你的方法下，最大的城市数可能是20，21或者22，但是连25都不可能。这是因为你的算法里面status的个数是n*(2^n)，当n=20的时候，大概是10个^7，当n=25时，大约是10^9，这是一个很大的数字。使用现代计算机，它可以在 1 秒内处理大约 10^7 个计算。但是处理 10^9 的计算大约需要 100 秒。

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