無向中国人郵便配達問題

説明

グラフの全ての辺を少なくとも一度通る単純とは限らない閉路の中で，最短のものを求める問題を中国人配達問題という．グラフがオイラー閉路を持つならばそれが答えとなる．そうではない場合はグラフにできるだけ短い辺を追加してオイラーとなるようにする（オイラー補完）．

無向グラフがオイラー閉路を持つための必要十分条件は，奇点が無いことだった．そこで，グラフの奇点の間の最短経路長を長さとするような完全グラフを作る．この上で最小重みマッチングを求め，得られたマッチングに対応する最短経路をもとのグラフに付け足せば，最小オイラー補完となる．

一般グラフの最小重みマッチングは理論的には多項式時間で解けるが，決して簡単ではないため，ここでは動的計画法に基づく単純なアルゴリズムを示す．

計算量

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

使い方

始点と終点を特定しない，単純とは限らないパスを求める場合は，プログラム中の best の初期化のところで best[{i,j}] = 0 を追加しておけばよい．始点や終点を特定したパスを求める場合も同様の修正で行える．

ソースコード

Weight chinesePostman(const Graph &g) {
  Weight total = 0;
  vector<int> odds;
  REP(u, g.size()) {
    FOR(e, g[u]) total += e->weight;
    if (g[u].size() % 2) odds.push_back(u);
  }
  total /= 2;
  int n = odds.size(), N = 1 << n;
  Weight w[n][n]; // make odd vertices graph
  REP(u,n) {
    int s = odds[u]; // dijkstra's shortest path
    vector<Weight> dist(g.size(), INF); dist[s] = 0;
    vector<int>    prev(g.size(), -2);
    priority_queue<Edge> Q;
    Q.push( Edge(-1, s, 0) );
    while (!Q.empty()) {
      Edge e = Q.top(); Q.pop();
      if (prev[e.dst] != -2) continue;
      prev[e.dst] = e.src;
      FOR(f,g[e.dst]) {
        if (dist[f->dst] > e.weight+f->weight) {
          dist[f->dst] = e.weight+f->weight;
          Q.push(Edge(f->src, f->dst, e.weight+f->weight));
        }
      }
    }
    REP(v,n) w[u][v] = dist[odds[v]];
  }
  Weight best[N]; // DP for general matching 
  REP(S,N) best[S] = INF;
  best[0] = 0;

  for (int S = 0; S < N; ++S)
    for (int i = 0; i < n; ++i) if (!(S&(1<<i)))
      for (int j = i+1; j < n; ++j) if (!(S&(1<<j)))
        best[S|(1<<i)|(1<<j)] = min(best[S|(1<<i)|(1<<j)], best[S]+w[i][j]);
  return total + best[N-1];
}

Verified

• UVA 11156，ただし任意パスなので best[{i,j}] = 0 を追加．