最短ハミルトン路

説明

最短ハミルトン路問題とは，グラフが与えられたとき，全ての頂点を一度ずつ通るパスで，経路長が最短のものを求める問題である．求めるものがパスでなく，サイクルである場合は最短ハミルトン閉路，もしくは巡回セールスマン問題という．

この問題は（判定問題として）NP 完全であることが知られているので，多項式時間の解法は期待できない．単純に全ての経路を試すアルゴリズムは O(V!) の計算量がかかるが，動的計画法に基づくアルゴリズムによって O(V^2 2^V) の計算量に軽減できる：

best[S + {j}][j] = best[S][i] + w[i][j]

ここで best[S][i] は S のすべての頂点を経由して i に到達したときの最小重みパスである．これによって，始点 s から終点 t に至る最小重みパスを計算することができる．閉路として求めたい場合は，最後に終点から始点への重みを足してやればよい．

計算量

O(n^2 2^n)．-O2 をかけて n ≦ 18 程度が限界．

使い方

Weight shortestHamiltonPath(Matrix w, int s, vector<int> &path)

Matrix w

隣接行列．枝が無い場合は +∞

int s

始点

vector<int> &path

最短ハミルトン路

戻り値

最短ハミルトン路の長さ．

ソースコード

const int M = 20;
Weight best[1<<M][M];
int    prev[1<<M][M];
void buildPath(int S, int i, vector<int> &path) {
  if (!S) return;
  buildPath(S^(1<<i), prev[S][i], path);
  path.push_back(i);
}
Weight shortestHamiltonPath(Matrix w, int s, vector<int> &path) {
  int N = 1 << n;
  REP(S,N) REP(i,n) best[S][i] = INF;
  best[1<<s][s] = 0;
  REP(S,N) REP(i,n) if (S&(1<<i)) REP(j,n)
    if (best[S|(1<<j)][j] > best[S][i] + w[i][j])
      best[S|(1<<j)][j] = best[S][i] + w[i][j],
      prev[S|(1<<j)][j] = i;
  int t = min_element(best[N-1], best[N-1]+n) - best[N-1];
  path.clear(); buildPath(N-1, t, path);
  return best[N-1][t];
}

Verified

• 問題は忘れたが三問以上で veriifed.