linear assignment problem について
Hungarian algorithm が有名所。scipy はこのアルゴリズムで実装されている。
>>> cost = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]]) >>> from scipy.optimize import linear_sum_assignment >>> row_ind, col_ind = linear_sum_assignment(cost) >>> col_ind array([1, 0, 2]) >>> cost[row_ind, col_ind].sum() 5
- Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing, vol. 38, pp. 325-340, 1987.
This paper is not publicly available though a brief description exists on sciencedirect.com. JV is faster in than the Hungarian algorithm in practice, though the complexity is the same - O(n3).