带有Held和Karp算法的旅行推销员

Question

我很清楚DP解决旅行商问题; 也被称为TSP的Held和Karp算法.

我用bitmask实现了它,它是这样的:

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。这是因为你的算法中的状态数量是n*(2^n)，当n=20时，大约是10 ^7，当n=25时，大约是10^9，这是一个非常大的数字。现代计算机可以在 1 秒内处理大约 10^7 次计算。但处理10^9的计算大约需要100秒。

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