巡回セールスマン問題をbitDPで解いてみる

巡回セールスマン問題（TSP: Traveling Salesman Problem）とは、「都市の集合と各2都市間の移動コストが与えられたとき、全ての都市をちょうど一度ずつ巡り出発点に戻る巡回路のうちで移動コストが最小のものを求める組み合わせ最適化問題である」（Wikipediaより引用）。

例えば、4都市の場合で、各都市間の移動コストが与えられた場合、





のような最小の移動コストを求める問題となります。この巡回セールスマン問題に対して、bitDPによる解法を解説してみます。（実装はC言語で記述していきます。）

移動経路の数とスタート位置

都市の数がNの場合、スタートする都市はN通りあり、その次に行く都市はN-1通り、…、となるので、経路はN!通りある。ただし、巡回する、すなわち経路が閉じるので、巡回経路の中のどの都市からスタートしても移動コストは変わらない。



したがって、巡回経路の通りの数は、(N-1)!通りになる。3都市の場合は(3-1)!=2通りとなり、1→2→3→1と1→3→2→1（左回りと右回り）の2通りである。各2都市間の移動コストが移動の向きによらず同じであれば左回りと右回りの移動コストは同じなので半分になり、結局、N都市を巡回する場合の移動コストは、(N-1)!÷2通りとなる。

これを総当たりで行うと、10都市で(10-1)!÷2=181440通り、20都市では
(20-1)!÷2=6.0822550204416×10¹⁶となる。

訪問都市の遷移

都市の数がNとして、都市に0～(N-1)の数字を割り付ける。
どの都市からスタートしてもよいので、スタートする都市を都市0に固定する。

4都市の場合で考えると、都市0からの経路は3（= N-1）通り、その次の経路は6（= (N-1)×(N-2)）通り、さらにその次の経路は6（= (N-1)×(N-2)×(N-3)）通りある。


ここで、最後の6通りのうち、0→2→3→1と0→3→2→1の経路について見てみる。都市1から次の都市への移動では、どちらの移動経路でも移動コストは同じであるから、この2つの経路の移動コストの大小関係は維持される。これは、「都市0, 1, 2, 3を訪問して、最後に訪問したのが都市1である経路のうち、移動コストが最小の経路」のみを考えればいいということである。



そうすると、6通りの経路を3通りに減らすことができる。以後についても同様に、「都市...を訪問して、最後に訪問した都市が...である経路」のうち移動コストが最小の経路のみを考えることにする。

訪問都市をbitで管理する

「都市...を訪問して」については、訪問の順序は関係ないので、訪問したかどうかを管理できればよい。とすると、都市の数がNの場合、訪問した、しない、の場合の数は2^N通りあるが、これを、各都市に対応するbitを用意し、各bitの0, 1で訪問した、しないを管理する。

0001 : 都市0のみを訪問した
0010 : 都市1のみを訪問した
0011 : 都市0と1を訪問した
0100 : 都市2のみを訪問した
0101 : 都市0と2を訪問した
0110 : 都市1と2を訪問した
0111 : 都市0と1と2を訪問した
1000 : 都市3のみを訪問した
1001 : 都市0と3を訪問した
1010 : 都市1と3を訪問した
1011 : 都市0と1と3を訪問した
1100 : 都市2と3を訪問した
1101 : 都市0と2と3を訪問した
1110 : 都市1と2と3を訪問した
1111 : 都市0と1と2と3を訪問した

というようにして、訪問都市をbitで管理できる。

最後に訪問した都市

訪問都市の組み合わせが2^N通りに対して、最後に訪問した都市はN通りである。そこで、「都市...を訪問」をbitで管理、「最後に訪問した都市」を0...N-1で管理する。

0001, 0 : 都市0のみを訪問して、最後に訪問したのが都市0
0010, 1 : 都市1のみを訪問して、最後に訪問したのが都市1
0011, 0 : 都市0と1を訪問して、最後に訪問したのが都市0
0011, 1 : 都市0と1を訪問して、最後に訪問したのが都市1
...

のように、N bitの2^N通りの組み合わせと、0...N-1のN通りの組み合わせで「都市...を訪問して、最後に訪問したのが都市...である」を表すことができた。

DPの遷移

「都市...を訪問して、最後に訪問したのが都市...である」経路の移動コストの最小値を、

　"dp[都市...を訪問した][最後に訪問したのが都市]"

で表すことにする。
そうすると、DPの遷移は、

• dp[0001][0]について、都市0から1への移動を追加すると、訪問した都市は0001+0010、最後に訪問した都市は1、移動コストに0→1の移動コストが加算される。
• dp[0011][1]から、都市2への移動を追加すると、訪問した都市は0011+0100、最後に訪問した都市は2、移動コストに1→2の移動コストが加算される。
• dp[0111][2]から、都市3への移動を追加すると、訪問した都市は0111+100、最後に訪問した都市は3、移動コストに2→3の移動コストが加算される。
• dp[0111][2]に都市2→3の移動を追加する場合の移動コストと、dp[0111][1]に都市1→3の移動を追加する場合の移動コストの最小値が、dp[1111][3]となる。

このDPの遷移を図に表すとこのようになる。（赤枠は、上の説明に該当する部分）

実装

訪問した都市を管理するbitは、for文で都市の全組み合わせを回す。ここで、i（添え字）が1からスタートしているのは、都市0をスタートとして固定しているから。

for (int i = 1; i < 1<<N; i++) {

}

訪問した都市の組み合わせのうち、最後に訪問した都市について、0～N-1をfor文で回す。

for (int i = 1; i < 1<<N; i++) {
  for (int j = 0; j < N; j++) {

  }
}

次に訪問する都市について、0～N-1をfor文で回す。ただし、次に訪問する都市が、すでに訪問した都市に含まれている場合は除いて、dpを遷移する。

for (int i = 1; i < 1<<N; i++) {
  for (int j = 0; j < N; j++) {
    for (int k = 0; k < N; k++) {
      if (i & (1<<k))
        continue;
      dp[i + (1<<k)][k] = min(dp[i][j] + cost[j][k], dp[i + (1<<k)][k]);
    }
  }
}

dpの遷移は以下のようになっている。

• 訪問した都市に都市kが追加されるので、訪問した都市のbitは、i+(1<<k)となる。
• そして、最後に訪問した都市は都市ｋになる。
• 最後に訪問した都市がjの移動コストに、都市jからkの移動を追加、新たな移動コストがdp[i][j] + cost[j][k]となる
• dp[i < (1<<k)][k]となる移動経路のうち、移動コストが最小のものでdpを更新する
• dpを最小値で更新していくので、dpは十分大きな値で初期化しておく。dp[1][0]（都市0を訪問して、最後に訪問した都市が0である経路の最小移動コスト）のみ0で初期化する

ここで、cost[j][k]は、都市jからkの移動コストであり、例えば、

int N, M;
scanf("%d %d", &N, &M);
int cost[N][M];
for (int i = 0; i < M; i++) {
  int u, v, c;
  scanf("%d %d %d", u, v, c);
  cost[u][v] = c;
  cost[v][y] = c;
}

として与えられている。

計算量

bitDPを使うと、都市の数がNの場合のdpの遷移数は(2^N)×N通りである。総当たりの場合と比較すると、

N=10 : 10240（総当たりの場合、181440）

N=20 : 20971520 = 2.0971520×10⁶（総当たりの場合、6.0822550204416×10¹⁶）

と小さくなっているが、それでもN=20あたりが計算量の上限になりそうである。