最小重み最大マッチング

説明

最小重み完全マッチングは多項式時間で解ける（Edmonds による花分解に基づくアルゴリズム）．しかし，それは複雑なので以下ではバックトラックによる解法を示す．

頂点を一つづつ選び，それをマッチする辺を適当に取って再帰，バックトラックする．これに安いほうから辺を選択するヒューリスティクスを導入した．これによって小さなサイズの問題は解けるようになる．

ちなみに動的計画法による解法（ best[S+u+v] = best[S] + adj[u][v] ）も知られているが．こちらは V ≦ 20 程度が限界になる．バックトラックではもう少し広く（ ≦30 ）取れる．

計算量

O(2^(V^2))．実用的には V < 30 程度で動く．

使い方

Weight minimumWeightMatching()

最小重み完全マッチングを求める．グラフサイズはグローバル変数 size, 辺重みはグローバル配列 adj に入れておくこと．

ToDo

• 簡潔な多項式解法？

ソースコード

// adj[i][j] = w(i,j)
Weight adj[N][N];
int size, sorted[N][N], num[N];
void rec(int match[], int p, int l, Weight w, Weight &opt) {
  int q = p + 1, i;
  if (w >= opt) return;
  for (; q < size; ++q) if (match[q] == -1) break;
  int m = num[q], *list = sorted[q];
  REP(j,m) if (match[i=list[j]] == -1) { // process greedily
    match[q] = i, match[i] = q;
    w += adj[i][q];
    if (l + 1 < size / 2) rec(match, q, l+1, w, opt);
    else opt = min(opt, w);
    w -= adj[i][q];
    match[q] = -1, match[i] = -1;
  }
}
int gs;
bool compareWith(int i, int j) { return adj[gs][i] < adj[gs][j]; }
Weight minimumWeightMatching() {
  for (gs = 0; gs < size; ++gs) { // sort adjacent nodes by edge weight
    for (int j = gs+1; j < size; ++j)
      sorted[gs][num[gs]++] = j;
    sort(sorted[gs], sorted[gs]+num[gs], compareWith);
  }
  int match[size]; fill(match, match+size, -1);
  Weight opt = INF;
  rec(match, -1, 0, 0, opt);
  return opt;
}

参考までに動的計画法に基づく解法も示す．n ≦ 15 程度ではこちらのほうが高速．

Weight best[1<<26];
int minimumWeightMatching() {
  fill(best, best+(1<<size), INF);
  best[0] = 0;
  for (int S = 0; S < (1<<size); ++S) {
    int i;
    for (i = 0; S & (1<<i); ++i);
    for (int j = i+1; j < size; ++j) {
      if (S & (1<<j)) continue;
      best[S + (1<<i) + (1<<j)] =
        min(best[S + (1<<i) + (1<<j)], best[S] + adj[i][j]);
    }
  }
  return best[(1<<size)-1];
}
  

Verified

• UVA 10296