割当問題（ハンガリー法）

$n \times n$ の費用表で、各行・各列の最小値を引く変形と、0 を最少の線で覆う操作をくり返し、総費用を最小にする割当とその最小値を求められる

前提

最大マッチングとケーニヒの定理（大学数学グラフ理論）

この技能までの道筋（9 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）
2 部グラフと奇閉路（大学数学グラフ理論）
最大独立集合と最小頂点被覆（大学数学グラフ理論）
最大マッチングとケーニヒの定理（大学数学グラフ理論）

説明

$n$ 人に $n$ 個の仕事を 1 人 1 つずつ割り当て、総費用を最小にする問題を割当問題といいます。費用表（ $n \times n$ の表）の第 $i$ 行第 $j$ 列を $a_{ij}$ （人 $i$ が仕事 $j$ をするときの費用）とします。すると割当問題は、各行・各列からちょうど 1 つずつ成分を選んで、その和を最小にする問題になります。選び方は $n!$ 通りあり、 $n$ が大きいと全部は調べられません。ハンガリー法は、表の変形と 2 部グラフの最大マッチングを組み合わせて、最適な割当とその最小費用を効率よく求める方法です。

なぜそうしてよいのか

行・列から定数を引いても、最適な割当は変わりません。 どの割当も各行・各列からちょうど 1 つずつ成分を選びます。そのため第 $i$ 行の全成分から $c$ を引くと、どの割当の総費用もちょうど $c$ だけ減ります。列についても同じです。したがって、各行・各列から最小値を引いた表で最適な割当は、元の表でも最適です。変形後の表の成分はすべて $0$ 以上です。よって値 $0$ の成分だけを使う割当が見つかれば、その総費用は $0$ でこれ以上小さくできず、その割当が最適です。

0 だけで割当できるかは、最大マッチングの問題です。 行を表す頂点と列を表す頂点を用意し、成分が $0$ の行と列を辺で結ぶと、2 部グラフ（0 のグラフ）ができます。0 だけを使う割当は、このグラフの大きさ $n$ のマッチングそのものです。また「0 をすべて覆う行・列の線」は、このグラフの頂点被覆そのものです。ケーニヒの定理より、線の最少本数 $k$ は最大マッチングの大きさ $ν$ に等しくなります。

最少の線は、最大マッチングから次のように作れます。 マッチングに使われていない行をすべて出発点にします。そこから「行→列は $0$ の辺」「列→行はマッチングの辺」をたどり、到達できる頂点をすべて求めます。そのうえで、到達できない行と到達できる列に線を引きます。
- これで $0$ はすべて覆われます。成分 $(i, j)$ が $0$ で行 $i$ に到達できるなら、列 $j$ にも到達できるので列の線で覆われます。行 $i$ に到達できないなら、行の線で覆われます。
- 線の本数は $ν$ です。到達できる列はどれもマッチングに使われています（使われていなければ増加道ができ、最大であることに反します）。その相手の行には到達できます。到達できない行は出発点でないので、マッチングに使われています。こうして各線にはそれぞれ別のマッチング辺が対応するので、本数は $ν$ 以下です。被覆なので $ν$ 以上でもあり、ちょうど $ν$ 本になります。

$k < n$ のときの調整。 線で覆われていない成分の最小値を $m$ とします（覆われていない成分はすべて正なので $m > 0$ ）。覆われていない各行から $m$ を引き、線を引いた各列に $m$ を足します。これは行・列の定数の足し引きなので、最適な割当は変わりません。成分ごとに見ると、次のようになります。
- 覆われていない成分は $- m$
- 縦横 2 本の線が交わる成分は $+ m$
- 1 本の線だけが通る成分はそのまま

このとき成分は $0$ 以上のままで、新しい $0$ が少なくとも 1 つできます。線を引いた行を $r$ 本、列を $c$ 本（ $r + c = k$ ）とすると、どの割当の総費用も $m (n - r) - m c = m (n - k) > 0$ だけ減ります。費用が整数なら、それまでに引いた量の合計は 1 回ごとに 1 以上増えます。この合計は最小費用を超えないので、操作は有限回で終わります。

手順

各行から、その行の最小値を引く。
次に各列から、その列の最小値を引く。これで各行・各列に少なくとも 1 つ $0$ ができ、成分はすべて $0$ 以上になる。
$0$ の位置で 2 部グラフを作る（成分が $0$ の行と列を辺で結ぶ）。増加道を使って最大マッチングを求め、その大きさを $ν$ とする。
最少の線を作る。マッチングに使われていない行から出発し、行→列は $0$ の辺、列→行はマッチングの辺をたどって、到達できる頂点を求める。到達できない行と到達できる列に線を引くと、 $0$ をすべて覆うちょうど $ν$ 本の線になる。
$ν = n$ なら、大きさ $n$ のマッチング（各行・各列から 1 つずつ選んだ $0$ ）が最適な割当である。元の費用表でその成分の和を計算して答える。
$ν < n$ なら、覆われていない成分の最小値 $m$ を求める。覆われていない成分から $m$ を引き、線が交わる成分に $m$ を足す（1 本だけが通る成分はそのまま）。その後、手順 3 に戻る。

例題

3 人 A, B, C を 3 つの仕事 1, 2, 3 に 1 人 1 つずつ割り当てる。費用表（行が人、列が仕事）は $423102352$ である（例えば A が仕事 1 をすると費用 4）。総費用の最小値を求めよ。

例題の解答

手順 1（行の最小値を引く）：各行の最小値は A: 1, B: 0, C: 2。引くと $321000250$
手順 2（列の最小値を引く）：列の最小値は 1, 0, 0。第 1 列から 1 を引くと $210000250$
手順 3（最大マッチング）： $0$ の位置は A–2, B–2, C–1, C–2, C–3。まず A–2, C–1 を選ぶ。B の $0$ は列 2 だけで、列 2 の相手 A の $0$ も列 2 だけなので、B から増加道はない。よって最大マッチングは A–2, C–1 で、 $ν = 2$ 。
手順 4（最少の線）：使われていない行 B から出発する。B→列 2（ $0$ の辺）、列 2→A（マッチング辺）とたどる。A の $0$ は列 2 だけで、ほかには進めない。到達できるのは行 A, B と列 2。到達できない行 C と到達できる列 2 に線を引くと、 $0$ はすべて覆われ、線は $ν = 2$ 本になる。
手順 5： $ν = 2 < 3$ なので、まだ最適ではない。
手順 6（調整）：覆われていない成分は A–1 の 2, A–3 の 2, B–1 の 1, B–3 の 5 で、最小値は $m = 1$ 。これらから 1 を引き、線の交点 C–2 に 1 を足すと $100001140$
手順 3 に戻る： $0$ の位置は A–2, B–1, B–2, C–1, C–3。A–2, B–1, C–3 は大きさ 3 のマッチングなので $ν = 3$ 。
手順 5： $ν = n$ なので、最適な割当は A→仕事 2, B→仕事 1, C→仕事 3。元の費用表で総費用は $1 + 2 + 2 = 5$ 。
（確認：引いた量の合計は、行 $1 + 0 + 2 = 3$ 、列 $1$ 、調整 $m (n - k) = 1 \cdot (3 - 2) = 1$ で、 $3 + 1 + 1 = 5$ となり一致する。）

答え: $5$

よくある誤り

$0$ が $n$ 個以上あれば最適だと判断してしまう誤り。正しくは、各行・各列から 1 つずつ選べる $0$ が $n$ 個あること（0 のグラフの最大マッチングの大きさが $n$ ）が条件である。例題の表 $210000250$ には $0$ が 5 個あるが、A と B の $0$ が同じ列にあるので、選べるのは 2 個までである。
線を手当たり次第に引いたり、到達できる頂点の扱いを逆にしたりする誤り。例えば上の表で「到達できる行 A, B と到達できない列 1, 3」に線を引くと 4 本になり、最少にならない。3 本の行の線で覆って「3 本必要だから最適」とするのも誤りである。正しくは、到達できない行と到達できる列に線を引く。この表では行 C と列 2 の 2 本（ $= ν$ ）で足りる。
調整で、すべての成分から $m$ を引いたり、線の交点に $m$ を足すのを忘れたりする誤り。正しくは、覆われていない成分は $- m$ 、線が 2 本交わる成分は $+ m$ 、1 本だけが通る成分はそのままである。交点に足し忘れると、例題では C–2 が $0$ のままになる。これは行・列の定数の足し引きになっていないので、最適な割当が変わってしまうことがある。
最後に変形後の表の成分を足して、最小費用を $0 + 0 + 0 = 0$ と答えてしまう誤り。正しくは、変形後の表は割当を決めるためだけに使い、総費用は元の費用表の成分で計算する（例題では $a_{A 2} + a_{B 1} + a_{C 3} = 1 + 2 + 2 = 5$ ）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

	$J_{1}$	$J_{2}$	$J_{3}$	$J_{4}$
$W_{1}$	$8$	$4$	$7$	$6$
$W_{2}$	$5$	$9$	$6$	$3$
$W_{3}$	$7$	$6$	$10$	$8$
$W_{4}$	$6$	$7$	$5$	$9$

	$J_{1}$	$J_{2}$	$J_{3}$	$J_{4}$	$J_{5}$
$W_{1}$	$t$	$7$	$9$	$8$	$11$
$W_{2}$	$6$	$10$	$4$	$9$	$7$
$W_{3}$	$9$	$5$	$8$	$6$	$10$
$W_{4}$	$4$	$8$	$7$	$11$	$6$
$W_{5}$	$8$	$9$	$6$	$7$	$5$

割当問題（ハンガリー法）

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題