Spaghetti Source logo

最短ハミルトン路

説明

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

この問題は(判定問題として)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

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.11.25 09:12:48.