PythonのMunkresを用いて割り当て問題を解く

【例題】以下の行列の各行から1つの数を選んで足した最小値を求めよ。ただし各列からは1つしか選べない。

	A	B	C	D	E
a	765	530	183	439	863
b	497	383	563	790	973
c	287	630	343	169	583
d	627	343	773	959	943
e	767	473	103	699	303

これをまともに解くとO(n!)となりますが、以下の記事を参考にしてPython のMunkresを使ってみました。

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

まずmunkresをインストールします。

pip install munkres

あとは行列をMunkresに渡すだけという簡単なものです。注意点はarrayをMunkresに渡すと中の値が変更されてしまうのでcopyしてから渡したほうが良いですね。

from munkres import Munkres
import numpy as np
import copy

mtx = np.array([[765,  530, 183, 439, 863],
[497, 383, 563,  790, 973],
[287,  630, 343, 169, 583],
[627, 343, 773, 959, 943],
[767, 473, 103, 699, 303]])

ansMtx = Munkres().compute(copy.copy(mtx))
asum = sum([mtx[idx] for idx in ansMtx])
print(ansMtx)
print(f"Minmum sum = {asum}")
#[(0, 2), (1, 0), (2, 3), (3, 1), (4, 4)]
#Minmum sum = 1495

これはProject Euler P345を解くのに役に立ちました。