【数理最適化】Hungarian Algorithm / ハンガリアン法

yhayato1320.hatenablog.com

Hungarian Algorithm / ハンガリアン (ハンガリー) 法 とは

割当・マッチング問題を解くためのアルゴリズムのひとつ.

2 部グラフの (重みなし) 最大マッチング問題は、最大流問題を解くことで求めることができる.

ハンガリアン法は、2部グラフの最大重みマッチング問題をとく方法であるが、
ここでは、説明を簡単にするために完全 2 部グラフの最大重み完全マッチング問題を対象とする.

完全 2 部グラフの最大重み完全マッチング問題

完全 2 部グラフ に対し、選ばれた辺の重み和が最大となる完全マッチングを求めよ.

アルゴリズム

1. 1. 重み行列の全成分の最大の値を としたとき、
      各成分 を で置き換え、すべての成分を非負にする.
   2. 各行ごとにその行の最小値をその行の成分から引く.
   3. さらに、各列ごとにその列の最小値をその列の成分から引く.
2. 値が 0 の成分だけを選んで、完全マッチングができれば、それが最適なマッチングとなるので終了する.
3. 0 をふくんでいる成分がなくなるように、行と列を削除する.
   そのとき、削除する行と列の本数の和が最小になるようにする.
4. 消されずに残った部分行列に対し、部分行列の成分の中の最小値を部分行列の各成分から引く.
   また、消された行と消された列の重なっている部分の各成分には、その最小値を足す.
   消した行と列を戻し、ステップ 2 に戻る.

参考

• The Hungarian method for the assignment problem
  • [1955] Hungarian Algorithm について
  • https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf

書籍

• 組合せ最適化
  • 3 組合せ最適化のアルゴリズム
    • 3.2 マッチング問題のアルゴリズム
      • 3.2.2 ハンガリー法

  • 今日から使える!組合せ最適化 離散問題ガイドブック (KS理工学専門書)

Web サイト

• 割当問題のハンガリアン法をpythonで実装してみた
  • qiita.com