every blog every motto: You can do more than you think.
https://blog.csdn.net/weixin_39190382?type=blog

0. 前言

分配问题小结，
linear_sum_assignment 函数使用的是Jonker-Volgenant algorithm算法

1. 分配问题

有工人和相应的工作，每个工作都有相应的成本，每个工人也有相应的成本，现在要安排工人去工作，使得总成本最小。

如下是成本矩阵C：

worker	job 1	job 2	job 3	job 4
A	43.5	47.1	48.4	38.2
B	45.5	42.1	49.6	36.8
C	43.4	39.1	42.1	43.2
D	46.5	44.1	44.5	41.2
E	46.3	47.8	50.4	37.2

形式上，令X XX为布尔矩阵，其中 X [ i , j ] = 1 X[i,j]=1X[i,j]=1 如果第 i ii 行分配给第j jj列。那么最优分配的成本:

具体实现，使用的是Jonker-Volgenant算法，该算法在1959年被提出，该算法基于动态规划，其时间复杂度为O(n^3)。

也可以使用之间介绍的匈牙利匹配算法。

2. 案例代码

import numpy as np
cost = np.array([[43.5, 45.5, 43.4, 46.5, 46.3],
                 [47.1, 42.1, 39.1, 44.1, 47.8],
                 [48.4, 49.6, 42.1, 44.5, 50.4],
                 [38.2, 36.8, 43.2, 41.2, 37.2]])

from scipy.optimize import linear_sum_assignment
row_ind, col_ind = linear_sum_assignment(cost)

row_ind 和 col_ind 是成本矩阵的最优分配矩阵索引：

row_ind
array([0, 1, 2, 3])

col_ind
array([2, 0, 3, 1])

3. 参考资料

1. https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html
2. https://www.cnblogs.com/happyamyhope/p/16644134.html