割当問題のハンガリアン法をpythonで実装してみた - Qiita割当問題とは？ 割当問題という問題をご存知でしょうか？ $n$ 人に $n$ 個の仕事を割り当てるとき、最も効率の良い割り当て方は何かを考える問題を「割当問題」といいます。 行列で考えるとわかりやすいです。下記の行列の行が人、列が仕事を表し、各成分は各人がそれぞれの仕事を終えるのにかかるコストととらえます。 各仕事に人は１人しか割り当てることができない状態で、全ての仕事に人を割り当てるとき、一番低コストな組み合わせを考えます。 このような問題を考える上で有名なアルゴリズムに「ハンガリアン法」（ハンガリー法）というものがあります。 step1 各行の各要素からその行の最小値を引き、その後さらに各列の各要素からその列の最小値を引く。 step2 $0$ を各行各列から１つずつ選ぶことができるかどうか判定する。もし選ぶことができれば、その $0$ の座標の組みが割当案となる。選ぶことができなれけ
