巡回セールスマン問題

\(N\)個のノード\(1, 2, ..., N\)を持つ重み付き有向グラフ\(G(V, E)\)について，ノード\(1\)から出発し，各ノードをちょうど1度ずつ通りノード\(1\)へ戻る閉路の中で最短の経路の距離を求めよ．

この問題はNP困難というクラスに属する有名な問題で，多項式時間で解くアルゴリズムが存在しないとされている．bitDPというアルゴリズムを使うと，\(O(|V|^22^{|V|})\)で解くことができる．

具体的には以下の漸化式が成立する．

$$ dp[\mathbb{S}][v] = min_{u \in (\mathbb{S}\backslash \lbrace v \rbrace)}(dp[S\backslash \lbrace v \rbrace][u] + dist[u][v]) $$

自然言語でいうなら，「今まで訪れたノードの集合が\(\mathbb{S}\)で最後に訪れたノードが\(v\)になるような最短経路は，今までノードの集合が\(\mathbb{S}\backslash \lbrace v \rbrace\)で最後に訪れたノードが\(\mathbb{S}\backslash \lbrace v \rbrace\)に含まれるいずれかのノードであるような最短経路にそのノードから\(v\)への距離を足した値の最小値」．

この訪れたノードの集合をbitで持つ．この集合の状態数は\(2^|V|\)となり，最後に訪れたノードの状態数は\(|V|\)である．各状態から，次に通る都市を\(|V|\)通り探索するので，全体の計算量は\(O(|V|^22^{|V|})\)となる．

コード

i64 tsp(int n, vector<vector<int>> &dist) {
  vector<vector<i64>> dp(1<<n, vector(n, inf));
  dp[0][0] = 0;
  rep (bit, 1<<n) {
    rep (u, n) {
      if (!((bit >> u)&1) and bit + u != 0) continue;
      rep (v, n) {
        if ((bit >> v)&1) continue;
        chmin(dp[bit|(1<<v)][v], dp[bit][u] + dist[u][v]);
      }
    }
  }
  return dp[(1<<n)-1][0];
}