手作業でハンガリー法 Hangarian Algorithm

project euler #345 に、割り当て問題の解き方で、名前だけ聞いたことのある「ハンガリー法（Hangarian Algorithm）」ってのが使えそうなので、勉強がてらやってみた。ほぼ手作業で。

====

下の表は、問題文中のサンプル。

7	53	183	439	863
497	383	563	79	973
287	63	343	169	583
627	343	773	959	943
767	473	103	699	303

#345 は最大値を求める問題なので、それぞれの値を1000から引いて、大小関係を逆転させておく。

993	947	817	561	137
503	617	437	921	27
713	937	657	831	417
373	657	227	41	57
233	527	897	301	697

行ごとに、最小値を行の各要素から引く。下表のように各行に少なくとも一つ 0ができる。

856	810	680	424	0
476	590	410	894	0
296	520	240	414	0
332	616	186	0	16
0	294	664	68	464

同様の操作を列ごとに行う。これで行で見ても列で見ても、最低一つの 0 ができた。

856	516	494	424	0
476	296	224	894	0
296	226	54	414	0
332	322	0	0	16
0	0	478	68	464

上から順に行を調べて、取り消されていない 0 がただ一個だけあれば、その 0 に仮決めの印をつける（ここでは白い太字）。仮決めした 0 と同じ列の他の行に 0 がもしあれば、取り消し印（ここでは取り消し線）をつける。

856	516	494	424	0
476	296	224	894	0
296	226	54	414	0
332	322	0	0	16
0	0	478	68	464

同じことを列に対して行う。つまり左から順に列を調べて、取り消されていない 0 が一個だけある列ならば、その0 に仮決め印をつけて、他の列の同じ行に 0 があれば、取り消し印をつける。

（この例では、行への操作と列への操作を一巡するだけで終わったが、もしまだ仮決めにも取り消しにもなっていない 0 が残っていれば、また行の操作からやり直す。）

856	516	494	424	0
476	296	224	894	0
296	226	54	414	0
332	322	0	0	16
0	0	478	68	464

仮決めの 0 を含まない行に印をつける。その行に取り消しの 0 があればその列に印をつける。さらにその列に仮決めの 0 があれば、その行に印をつける。その行に取り消しの 0 が・・・って感じで、やることが無くなるまで続ける。（言葉にすると変だけど、やってみると簡単）

856	516	494	424	0
476	296	224	894	0	←
296	226	54	414	0	←
332	322	0	0	16
0	0	478	68	464

856	516	494	424	0
476	296	224	894	0	←
296	226	54	414	0	←
332	322	0	0	16
0	0	478	68	464
				↑

856	516	494	424	0	←
476	296	224	894	0	←
296	226	54	414	0	←
332	322	0	0	16
0	0	478	68	464
				↑

印がついていない行と、印がついた列に色をつける。ただし重なっている部分が分かるようにする。ここでは重なっていない部分を橙色、重なった部分を赤の文字色にした。

856	516	494	424	0	←
476	296	224	894	0	←
296	226	54	414	0	←
332	322	0	0	16
0	0	478	68	464
				↑

色がついていない部分の最小値（ここでは54）を見つけて、色がついていない値から減算し、重なっている値には加算する。色がついているけど重なっていない部分の値はそのまま。

できたら、いったん印とか色とかをクリアして、また印をつけるところからやり直す。各行、各列に一個ずつ 0 が決まったら終わり。

以下、もう一巡したところ。

802	462	440	370	0	←
422	242	170	840	0	←
242	172	0	360	0	←
332	322	0	0	70
0	0	478	68	518
				↑

さらに一巡

632	292	270	200	0
252	72	0	670	0	←
242	172	0	360	170	←
332	322	0	0	240
0	0	478	68	688
		↑		↑

もっかい

632	292	342	200	72	←
180	0	0	598	0
170	100	0	288	170
332	322	72	0	312
0	0	550	68	760

さらに半巡して、つまり、無色の値の最小値（72）を、それぞれの無色の値から減算したところで、やっと全ての行と列に 0 が揃った。

560	220	270	128	0
180	0	0	598	0
170	100	0	288	170
332	322	72	0	312
0	0	550	68	760

0 になっている部分の位置関係を、そっくりそのままもとの表に当てはめると、問題文どおりの値が得られる。

				863
	383
		343
			959
767

====

euler #345 だと 15×15 のマトリクスだけど、試しに手作業（＋Excel）でやってみたら、6 巡か 7 巡で、2時間以上かかったけど、まあ一応正答がでた。正直、ハンガリー法のやり方がよくわかっていなかったのでやたらと時間がかかったが、手でやった分、なんか身についた気がする。

Youtube にもハンガリー法の実演動画がたくさんあるけど、下記リンクのインドの大学の講義が、インド訛りをのぞけば一番懇切丁寧で参考になった。 Lec-16 Assignment Problem - Hungarian Algorithm

この問題は、手作業でできてしまったので、コーディングはまた今度にすることにしたけど、project euler の thread を見ると、なんだか各人各様でかなり異なるアイデアで解いている。そのうち調べて見ようと思う。特に DP を使っているやり方とか。