scipy.optimize.

linear_sum_assignment#

scipy.optimize.linear_sum_assignment()#

解决线性求和分配问题。

参数:
cost_matrix数组

二部图的成本矩阵。

maximize布尔值 (默认值: False)

如果为真，则计算最大权重匹配。

返回值:
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] 是匹配第一个 partite 集合（“工人”）的顶点 i 和第二个集合（“工作”）的顶点 j 的成本。目标是找到工人到工作的最小成本的完整分配。

正式地，令 X 为一个布尔矩阵，其中 \(X[i,j] = 1\) 当且仅当行 i 被分配到列 j 时。那么最佳分配的成本为

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

其中，在矩阵 X 为方形的情况下，每一行都分配到恰好一列，每一列都分配到恰好一行。

此函数还可以解决经典分配问题的推广，其中成本矩阵为矩形。如果它行数大于列数，那么并非每一行都需要分配到一列，反之亦然。

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

在版本 0.17.0 中添加。

参考文献

[2]

DF Crouse。关于实现二维矩形分配算法。IEEE 航空航天与电子系统汇刊，52(4):1679-1696，2016 年 8 月，DOI:10.1109/TAES.2016.140952

示例

>>> import numpy as np
>>> 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
本页内容