scipy.optimize.linear_sum_assignment¶

scipy.optimize.linear_sum_assignment(cost_matrix, maximize=False)[源代码]¶

解决线性和分配问题。

参数

cost_matrix阵列: 二部图的成本矩阵。
maximize布尔值(默认值：FALSE): 如果为True，则计算最大权重匹配。

退货

row_ind, col_ind阵列: 行索引数组和相应列索引中的一个给出最佳分配。分配的成本可以计算为 cost_matrix[row_ind, col_ind].sum() 。将对行索引进行排序；在平方成本矩阵的情况下，它们将等于 numpy.arange(cost_matrix.shape[0]) 。

参见

scipy.sparse.csgraph.min_weight_full_bipartite_matching: 对于稀疏输入

注意事项

线性和分配问题 [1] 在二部图中也称为最小权匹配。问题实例由矩阵C描述，其中每个C [i,j] 是匹配第一部分集的顶点i(工作者)和第二集的顶点j(作业)的成本。目标是找到一个完整的工人分配到成本最低的工作。

形式上，设X是布尔矩阵，其中 \(X[i,j] = 1\) 如果将行i分配给列j，则最优分配具有成本

\[\min\sum_i\sum_j C_{i，j}X_{i，j}\]

其中，在矩阵X为正方形的情况下，将每行恰好分配给一列，并且将每列恰好分配给一行。

该函数还可以解决成本矩阵为矩形的经典分配问题的推广。如果它的行数多于列数，则不需要将每行都分配给列，反之亦然。

该实现是没有初始化的修改的Jonker-Volgenant算法，在参考文献中描述。 [2].

0.17.0 新版功能.

参考文献

1: https://en.wikipedia.org/wiki/Assignment_problem
2: DF Crouse.关于二维矩形分配算法的实现。 IEEE航空航天和电子系统汇刊 ，52(4)：1679-1696,2016年8月， DOI:10.1109/TAES.2016.140952

示例

>>> 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

scipy.optimize.linprog_verbose_callback

scipy.optimize.quadratic_assignment