Spaghetti Source logo

割り当て問題(ハンガリアン法)

説明

人 1 ... n と仕事 1 ... n がある.人 i を仕事 j に割り当てたときの利益が a[i][j] であるとする.このとき,すべての人を,それぞれ異なる仕事につかせることによって,得られる利益を最大化する問題を割り当て問題という.

この問題は,二部グラフの最大重みマッチングの特殊な場合であると考えられる.すなわち,二部グラフの両側の頂点数が等しく,完全グラフである場合が割り当て問題である.ハンガリアン法は最小費用流問題に対する主双対法を,行列ベースで書き下したアルゴリズムだと理解することもできる.

計算量

O(n^3)

使い方

hungarian(matrix a)
割り当て問題の利益行列 a を与えたとき,最適割り当てを行ったときの利益を求める.matrix は typedef vector<vector<weight>>
vector<int> x(n), y(n)(内部変数)
x[i] は左側頂点 i に対応する右側頂点,y[j] は右側頂点 j に対応する左側頂点をそれぞれ表す.

ソースコード

weight hungarian(const matrix &a) {
  int n = a.size(), p, q;
  array fx(n, inf), fy(n, 0);
  vector<int> x(n, -1), y(n, -1);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      fx[i] = max(fx[i], a[i][j]);
  for (int i = 0; i < n; ) {
    vector<int> t(n, -1), s(n+1, i);
    for (p = q = 0; p <= q && x[i] < 0; ++p)
      for (int k = s[p], j = 0; j < n && x[i] < 0; ++j)
        if (fx[k] + fy[j] == a[k][j] && t[j] < 0) {
          s[++q] = y[j], t[j] = k;
          if (s[q] < 0)
            for (p = j; p >= 0; j = p)
              y[j] = k = t[j], p = x[k], x[k] = j;
        }
    if (x[i] < 0) {
      weight d = inf;
      for (int k = 0; k <= q; ++k)
        for (int j = 0; j < n; ++j)
          if (t[j] < 0) d = min(d, fx[s[k]] + fy[j] - a[s[k]][j]);
      for (int j = 0; j < n; ++j) fy[j] += (t[j] < 0 ? 0 : d);
      for (int k = 0; k <= q; ++k) fx[s[k]] -= d;
    } else ++i;
  }
  weight ret = 0;
  for (int i = 0; i < n; ++i) ret += a[i][x[i]];
  return ret;
}

Verified

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

Last Modified: 2007.10.20 10:00:57.