割当問題
概要
割当問題（assignment problem）とは、$n\times n$ の費用行列 $c$ について、$n$ 人に $n$ 個の仕事を 1 つずつ割り当てる置換 $\sigma$ のうち、費用 $\sum_ic_{i\sigma(i)}$ が最小のものを求める問題であり、完全二部グラフの重み最小の完全マッチングを求める問題と同じである。$u_i+v_j\le c_{ij}$ を満たすポテンシャルの値 $\sum u_i+\sum v_j$ はつねに最小費用以下で、割り当てた所で等号なら最適である。ハンガリー法は König の定理を使ってポテンシャルを改良し、費用が整数なら有限回で止まって最適な割り当てを与えるので、最小費用は整数のポテンシャルの値の最大値に等しい。
前提知識: 輸送問題, 二部グラフ, マッチング(グラフ理論), 置換
$n$ 人に $n$ 個の仕事を 1 つずつ割り当てる。人 $i$ が仕事 $j$ をする費用 $c_{ij}$ が分かっているとき、費用の合計が最小になる割り当て方を求めたい。これが 割当問題 である。割り当て方は $n!$ 通りあり、すべてを調べるのは $n$ が少し大きくなるだけで現実的でない。
割当問題は、供給量と需要量がすべて $1$ の輸送問題であり、線形計画法としての双対定理と、最適解が置換でとれること（Birkhoff–von Neumann の定理）は 輸送問題 の記事で証明されている。この記事では割当問題に固有の側面として、人と仕事に「値段」（ポテンシャル）を付けて最適性を確かめる方法を述べ、二部グラフのマッチングと頂点被覆についての König の定理を使って、ポテンシャルを少しずつ改良する ハンガリー法 が正しく止まることを証明する。その帰結として、費用が整数なら、最小費用は整数のポテンシャルの値の最大値に等しい。
定義
$n\ge1$ とし、$n$ 次の対称群（$\{1,\dots,n\}$ の置換全体）を $S_n$ と書く。
実数を成分とする $n\times n$ 行列 $c=(c_{ij})$（費用行列）について、置換 $\sigma\in S_n$ の 費用 を
$$
c(\sigma):=\sum_{i=1}^nc_{i\sigma(i)}
$$
とする。$c(\sigma)$ を最小にする $\sigma$ を求める問題を 割当問題（assignment problem）といい、最小にする $\sigma$ を 最適な割り当て という。
人 $x_1,\dots,x_n$ と仕事 $y_1,\dots,y_n$ を頂点とし、すべての $x_i$ と $y_j$ を結んだ完全二部グラフ $K_{n,n}$ の辺 $x_iy_j$ に重み $c_{ij}$ を付けると、置換 $\sigma$ は完全マッチング $\{x_iy_{\sigma(i)}\mid1\le i\le n\}$（マッチング(グラフ理論) の定義「辺集合のマッチング」）に対応し、$c(\sigma)$ はその重みの和である。したがって割当問題は、重み付きの完全二部グラフで重みの和が最小の完全マッチングを求める問題と同じである。重みの和を最大にしたいときは、$c_{ij}$ の符号を変えればよい。
$u=(u_1,\dots,u_n)$、$v=(v_1,\dots,v_n)$ を実数の組とする。
- すべての $i,j$ で $u_i+v_j\le c_{ij}$ のとき、$(u,v)$ を 実行可能なポテンシャル といい、$\lvert u\rvert+\lvert v\rvert:=\sum_iu_i+\sum_jv_j$ をその 値 という。
- $r_{ij}:=c_{ij}-u_i-v_j$ を $(u,v)$ に関する 被約費用 という。
- $r_{ij}=0$ となる辺 $x_iy_j$ だけからなる $K_{n,n}$ の全域部分グラフを、$(u,v)$ の 等号グラフ といい、$G_{u,v}$ と書く。
$u_i$ は人 $i$ に、$v_j$ は仕事 $j$ に付けた値段であり、実行可能性は「どの組でも 2 つの値段の和が費用を超えない」ことである。被約費用は、$c$ の第 $i$ 行から $u_i$ を、第 $j$ 列から $v_j$ を引いた行列の成分であり、実行可能なら $0$ 以上である。
$(u,v)$ を実行可能なポテンシャルとする。任意の $\sigma\in S_n$ について
$$
c(\sigma)-\bigl(\lvert u\rvert+\lvert v\rvert\bigr)=\sum_{i=1}^nr_{i\sigma(i)}\ge0
$$
である。とくに、$\sigma$ に対応する完全マッチングが等号グラフ $G_{u,v}$ に含まれるなら、$\sigma$ は最適な割り当てであり、$(u,v)$ は実行可能なポテンシャルのうち値が最大のものである。
$\sigma$ は全単射なので $\sum_iv_{\sigma(i)}=\sum_jv_j$ であり、$c(\sigma)-\sum_iu_i-\sum_jv_j=\sum_i(c_{i\sigma(i)}-u_i-v_{\sigma(i)})=\sum_ir_{i\sigma(i)}$ である。各項は実行可能性から $0$ 以上である。$\sigma$ の辺がすべて等号グラフにあれば右辺は $0$ なので、任意の $\sigma'$ と実行可能な $(u',v')$ について $c(\sigma')\ge\lvert u\rvert+\lvert v\rvert=c(\sigma)\ge\lvert u'\rvert+\lvert v'\rvert$ である。$\square$
この判定は、最大化の形で BM76 Theorem 5.5（pp. 86–87）にある（そこでの「実行可能な頂点のラベル」がポテンシャルにあたる）。
実数 $a_1,\dots,a_n$、$b_1,\dots,b_n$ について $c'_{ij}:=c_{ij}-a_i-b_j$ とおくと、すべての $\sigma\in S_n$ で $c'(\sigma)=c(\sigma)-\sum_ia_i-\sum_jb_j$ である。とくに $c$ と $c'$ の最適な割り当ては同じである。また $(u,v)$ が $c$ の実行可能なポテンシャルであることと、$(u-a,v-b)$ が $c'$ の実行可能なポテンシャルであることは同値で、その値の差も $\sum_ia_i+\sum_jb_j$ である。
$\sigma$ は全単射なので $\sum_ib_{\sigma(i)}=\sum_jb_j$ であり、$c'(\sigma)=\sum_i(c_{i\sigma(i)}-a_i-b_{\sigma(i)})=c(\sigma)-\sum_ia_i-\sum_jb_j$ である。差は $\sigma$ によらないので、最小にする $\sigma$ は同じである。後半は $c'_{ij}-(u_i-a_i)-(v_j-b_j)=c_{ij}-u_i-v_j$ による。$\square$
被約費用の行列は、$a=u$、$b=v$ としたときの $c'$ にほかならない。したがって、ポテンシャルを改良することは、行と列から定数を引いて、最適な割り当てを変えずに $0$ の成分を増やしていくことと言い換えられる。
割当問題は、輸送問題 で供給量と需要量をすべて $1$ にした問題であり、その実行可能解の全体は二重確率行列の全体である。輸送問題 の系「Birkhoff–von Neumann の定理」の 3 により、割当問題の最小値は、この輸送問題（線形計画問題）の最小値に等しい。さらに 輸送問題 の定理「輸送問題の双対定理」により、その最小値は実行可能なポテンシャルの値の最大値に等しい（輸送問題の双対問題は、ここでの $u_i+v_j\le c_{ij}$ のもとで $\lvert u\rvert+\lvert v\rvert$ を最大にする問題である）。この記事では、費用が整数の場合に、この等式を整数のポテンシャルで、線形計画法を使わずに証明する（thm-ap-integral）。
ハンガリー法
等号グラフに完全マッチングがあれば、lem-ap-weak により問題は解ける。ないときは、ポテンシャルを改良して等号グラフに辺を増やす。どこを改良するかを、等号グラフの最大マッチングと最小の頂点被覆が教える。二部グラフ $H$ のマッチングの大きさの最大値を $\nu(H)$、頂点被覆（どの辺も少なくとも一方の端点を含む頂点の集合）の大きさの最小値を $\tau(H)$ と書く。二部グラフでは $\nu(H)=\tau(H)$ である（König の定理、マッチング(グラフ理論) の定理「二部グラフの最大マッチングと最小頂点被覆」）。
ハンガリー法（行列の形）：
0. $u_i:=\min_jc_{ij}$、$v_j:=\min_i(c_{ij}-u_i)$ とおく（第 $i$ 行から行の最小値を、続いて各列から列の最小値を引く）。
- 等号グラフ $G_{u,v}$ の最大マッチング $M$ を求める。$\lvert M\rvert=n$ なら、$M$ に対応する置換を出力して止める。
- $\lvert M\rvert< n$ なら、$G_{u,v}$ の頂点被覆 $K$ で $\lvert K\rvert=\lvert M\rvert$ となるもの（最小の頂点被覆）をとり、$K$ に入る人の添字の集合を $R_K$、仕事の添字の集合を $C_K$ とする。
- $\delta:=\min\{r_{ij}\mid i\notin R_K,\ j\notin C_K\}$ とし、$i\notin R_K$ について $u_i\leftarrow u_i+\delta$、$j\in C_K$ について $v_j\leftarrow v_j-\delta$ とする。1 へ戻る。
手順 2 は、被約費用の行列で「$0$ の成分をすべて覆う、最も少ない本数の行と列」を選ぶことにあたる。手順 3 は、覆われない成分から $\delta$ を引き、2 回覆われる成分に $\delta$ を足すことにあたる。
- 手順 0 のポテンシャルは実行可能であり、手順 3 は実行可能性を保つ。$c$ の成分が整数なら、$u,v$ の成分はつねに整数である。
- 手順 3 に進むとき、$\nu:=\lvert M\rvert< n$ について $\delta>0$ であり、手順 3 でポテンシャルの値はちょうど $\delta\,(n-\nu)$ だけ増える。
- $c$ の成分が整数なら、手順は有限回で止まる。止まったとき、出力 $\sigma$ は最適な割り当てであり、そのときの $(u,v)$ は整数の実行可能なポテンシャルで $\lvert u\rvert+\lvert v\rvert=c(\sigma)$ を満たす。
1：手順 0 の $u$ では $c_{ij}-u_i\ge0$ であり、$v_j$ は第 $j$ 列のその最小値なので $c_{ij}-u_i-v_j\ge0$ である。手順 3 で被約費用 $r_{ij}$ は、$i\notin R_K$ かつ $j\notin C_K$ なら $\delta$ 減り、$i\in R_K$ かつ $j\in C_K$ なら $\delta$ 増え、ほかは変わらない。減る成分は $\delta$ の定め方から $r_{ij}\ge\delta$ なので、更新後も $0$ 以上である。$c$ が整数なら、手順 0 の $u,v$ は整数で、被約費用も $\delta$ も整数なので、整数のまま保たれる。
2：$M$ は最大マッチングなので、König の定理により $\lvert M\rvert$ 個の頂点からなる頂点被覆 $K$ があり、手順 2 は実行できる。$K$ は $G_{u,v}$ のすべての辺を覆うので、$i\notin R_K$ かつ $j\notin C_K$ となる $(i,j)$ は等号グラフの辺でなく、$r_{ij}>0$ である。$\lvert R_K\rvert+\lvert C_K\rvert=\nu< n$ なので、$R_K$ に入らない $i$ と $C_K$ に入らない $j$ がそれぞれ存在し、$\delta$ は正の数の有限個の最小値として定まり $\delta>0$ である。値の変化は
$$
\delta\,(n-\lvert R_K\rvert)-\delta\,\lvert C_K\rvert=\delta\,(n-\nu)
$$
である。
3：$c$ が整数なら、2 により手順 3 のたびに値は $1$ 以上増える。一方 lem-ap-weak により、値はつねに $\min_\sigma c(\sigma)$ 以下である。よって手順 3 は有限回しか起こらず、手順 1 で止まる。止まったときの $M$ は等号グラフの完全マッチングなので、lem-ap-weak により $\sigma$ は最適で、$\lvert u\rvert+\lvert v\rvert=c(\sigma)$ である。$u,v$ が整数であることは 1 による。$\square$
費用行列 $c$ の成分がすべて整数なら
$$
\min_{\sigma\in S_n}c(\sigma)=\max\Bigl\{\lvert u\rvert+\lvert v\rvert\Bigm|u,v\in\mathbb{Z}^n,\ u_i+v_j\le c_{ij}\ (\text{すべての }i,j)\Bigr\}
$$
であり、右辺の最大値は存在する。
lem-ap-weak により、整数の実行可能なポテンシャルの値はどれも左辺以下である。thm-ap-hungarian の 3 により、値が左辺に等しい整数の実行可能なポテンシャルがある。よって右辺の最大値は存在して左辺に等しい。$\square$
費用行列 $c$ の成分が実数なら、$\min_\sigma c(\sigma)$ は実行可能なポテンシャル（実数）の値の最大値に等しい。$c$ の成分が有理数なら、この最大値は有理数のポテンシャルで達成され、ハンガリー法は有限回で止まる。
有理数の場合：成分の分母の公倍数 $q\ge1$ をとると $qc$ は整数の行列である。$qc$ にハンガリー法を使うことと $c$ に使うことは、すべての数を $q$ 倍するだけの違いなので、手順は有限回で止まり、thm-ap-integral の $qc$ についての等式を $q$ で割れば主張を得る。実数の場合は rem-ap-transportation のとおり、輸送問題 の定理「輸送問題の双対定理」と系「Birkhoff–von Neumann の定理」の 3 による（この記事では証明しない）。$\square$
輸送問題 の記事の整数性は、供給量・需要量が整数のときの輸送計画（主問題の解）の整数性である。費用が整数のときにポテンシャル（双対問題の解）も整数でとれることは、この記事の thm-ap-integral で示した。最適な割り当てとポテンシャルは、互いの最適性を保証する。ポテンシャルを示されれば、$n!$ 通りを調べなくても、被約費用が $0$ 以上で割り当てた所が $0$ であることを確かめるだけで最適性が分かる。
計算の例
費用行列を
$$
c=\begin{pmatrix}2&4&3&7\\8&8&2&9\\7&4&8&5\\1&8&8&7\end{pmatrix}
$$
とする。
使う結果：thm-ap-hungarian、lem-ap-weak。
答え：最適な割り当ては人 $1,2,3,4$ に仕事 $2,3,4,1$ で、費用は $4+2+5+1=12$ である。$u=(4,3,4,3)$、$v=(-2,0,-1,1)$ は整数の実行可能なポテンシャルで、値は $14-2=12$ である。
手順 0 で $u=(2,2,4,1)$、$v=(0,0,0,1)$（値 $10$）となり、その後 2 回の改良で止まる。各段の被約費用の行列は次のとおりで、最後の行列では割り当てた所（太字）がすべて $0$、ほかは $0$ 以上である。
$$
\begin{pmatrix}0&2&1&4\\6&6&0&6\\3&0&4&0\\0&7&7&5\end{pmatrix}\;\to\;
\begin{pmatrix}0&1&0&3\\7&6&0&6\\4&0&4&0\\0&6&6&4\end{pmatrix}\;\to\;
\begin{pmatrix}0&\mathbf 0&0&2\\7&5&\mathbf 0&5\\5&0&5&\mathbf 0\\\mathbf 0&5&6&3\end{pmatrix}
$$
途中の手順を開く
1 回目：$0$ の成分は $(1,1),(2,3),(3,2),(3,4),(4,1)$ である。人 $1$ と人 $4$ はどちらも仕事 $1$ にしか $0$ がないので、等号グラフの最大マッチングは $\{(1,1),(2,3),(3,2)\}$ などで大きさ $3$ である。仕事 $1$ の列と人 $2$・人 $3$ の行の 3 本で $0$ がすべて覆われる（$R_K=\{2,3\}$、$C_K=\{1\}$）。覆われない成分（行 $1,4$、列 $2,3,4$）の最小値は $\delta=1$ で、$u_1,u_4$ に $1$ を足し、$v_1$ から $1$ を引く。$u=(3,2,4,2)$、$v=(-1,0,0,1)$、値は $10+1\cdot(4-3)=11$ になる。
2 回目：$0$ の成分は $(1,1),(1,3),(2,3),(3,2),(3,4),(4,1)$ である。人 $1,2,4$ の $0$ は仕事 $1$ と仕事 $3$ の 2 列にしかないので、この 3 人のうち少なくとも 1 人は割り当てられず、最大マッチングの大きさは $3$ である（たとえば $\{(2,3),(3,2),(4,1)\}$）。人 $3$ の行と仕事 $1$・仕事 $3$ の列で $0$ がすべて覆われる（$R_K=\{3\}$、$C_K=\{1,3\}$）。覆われない成分（行 $1,2,4$、列 $2,4$）の最小値は $\delta=1$ で、$u=(4,3,4,3)$、$v=(-2,0,-1,1)$、値は $12$ になる。
3 回目：$(1,2),(2,3),(3,4),(4,1)$ がすべて $0$ なので、等号グラフに完全マッチングがあり、止まる。$24$ 通りの割り当ての費用を全部並べても、最小は $12$ でこの割り当てだけが達成する。
問題の変形
- 最大化：重み $w_{ij}$ の和を最大にするには、$c_{ij}:=-w_{ij}$ として最小化すればよい。ポテンシャルの条件は $u_i+v_j\ge w_{ij}$ の形になり、BM76 §5.5（pp. 86–90）の「実行可能な頂点のラベル」はこの形である。
- 人と仕事の数が違う場合：$m$ 人（$m< n$）に $n$ 個の仕事から相異なる仕事を 1 つずつ割り当てる問題は、費用 $0$ の架空の人を $n-m$ 人加えた $n\times n$ の割当問題と同じである。実際、$m$ 人への単射な割り当ては、残りの仕事を架空の人に割り振れば置換に延長でき、費用は変わらない。逆に置換から架空の人の行を除けば単射な割り当てになる。
- マッチングとの関係：2 つの部 $\{x_1,\dots,x_n\}$、$\{y_1,\dots,y_n\}$ をもつ二部グラフ $H$ について、$x_iy_j$ が $H$ の辺なら $c_{ij}:=0$、そうでなければ $c_{ij}:=1$ とすると、$\min_\sigma c(\sigma)=n-\nu(H)$ である。$H$ の大きさ $\nu(H)$ のマッチングは、残りの人と仕事を任意に組んで置換に延長でき、その費用は $n-\nu(H)$ 以下である。逆に、置換の組のうち $H$ の辺であるものはマッチングをなすので、どの置換の費用も $n-\nu(H)$ 以上だからである。したがって割当問題が解ければ二部グラフの最大マッチングも求まる。
条件を外したときの反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 費用が整数（thm-ap-integral） | $n=1$、$c=(\tfrac12)$ | 整数のポテンシャルの値の最大値が最小費用に等しい |
| ポテンシャルが実行可能（lem-ap-weak） | $n=2$、$c=\begin{pmatrix}0&1\\1&0\end{pmatrix}$、$u=(1,1)$、$v=(0,0)$ | 値が最小費用以下である |
| 割り当てが置換である（仕事が重複しない） | $n=2$、$c=\begin{pmatrix}1&2\\1&2\end{pmatrix}$、$u=(1,1)$、$v=(0,1)$ で、2 人とも仕事 $1$ に割り当てる | 費用が実行可能なポテンシャルの値以上である（lem-ap-weak） |
| 手順 2 の頂点被覆が最小 | ex-ap-main の 1 回目で $K$ を 4 人全員の行にとる | 手順 3 の $\delta$ が定まる |
どの行も、左の条件だけを外している。
4 つの確認を開く
1 行目：最小費用は $\tfrac12$ である。整数 $u_1,v_1$ が $u_1+v_1\le\tfrac12$ を満たせば $u_1+v_1\le0$ なので、整数のポテンシャルの値の最大値は $0$ である。実数のポテンシャル $u_1=\tfrac12$、$v_1=0$ では値 $\tfrac12$ に達し、cor-ap-real と合っている。
2 行目：$u_1+v_1=1>c_{11}=0$ なので実行可能でない。値は $2$ だが、最小費用は恒等置換の $0$ である。
3 行目：$u_i+v_1=1\le c_{i1}=1$、$u_i+v_2=2\le c_{i2}=2$ なので $(u,v)$ は実行可能で、値は $3$ である。2 人とも仕事 $1$ に割り当てると費用は $2< 3$ だが、仕事 $1$ が重複していて置換ではない。置換の費用は $1+2$ と $2+1$ でどちらも $3$ で、値 $3$ 以上である。
4 行目：4 本の行はすべての成分を覆うので頂点被覆だが、大きさは $4>\nu=3$ である。覆われない成分がなく、$\delta$ が定まらない。最小の頂点被覆なら $\lvert R_K\rvert+\lvert C_K\rvert=\nu< n$ で、覆われない行と列が残る（thm-ap-hungarian の 2 の証明）。
補足
- 効率：thm-ap-hungarian の証明で示した改良の回数の上界は、費用の大きさに依存する。BM76 §5.5 は、等号グラフの中で交互木を育てて増加道を探しながらポテンシャルを改良する Kuhn–Munkres の方法を述べ、それが良いアルゴリズム（計算の手数がグラフの頂点数と辺数の多項式で抑えられるもの。同書 §1.8、p. 19 の意味）であることを示している（pp. 87–90。この記事では証明しない）。同書 §5.4（pp. 80–85）は、その中で使う二部グラフのマッチングの探し方をハンガリー法と呼んでいる。
- 一般の輸送問題：供給量・需要量が一般の場合は 輸送問題 であり、整数性と双対定理が同じ形で成り立つ。割当問題は、その頂点がちょうど置換行列になる場合である（輸送問題 の系「Birkhoff–von Neumann の定理」）。
- 二部グラフの上の流れ：割当問題は、二部グラフの上の最小費用流の問題としても定式化される（ネットワークフロー、二部グラフ）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
