5

私は、巡回セールスマンの問題に対する DP ソリューションをよく知っています。TSP の Held and 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) プルーニングに上限と下限の両方を使用する。上記のアルゴリズムは、非常に短い時間で最初の可能な最適解を得ることができ、それを使用できる可能性があります。

前述の 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 に答える