scipy.optimize.
linear_sum_assignment#
- scipy.optimize.linear_sum_assignment()#
求解线性分配问题。
- 参数:
- cost_matrix数组
二分图的成本矩阵。
- maximize布尔值 (默认值: False)
如果为 True,则计算最大权重匹配。
- 返回:
- row_ind, col_ind数组
一个包含行索引和相应列索引的数组,给出最优分配。分配的成本可以计算为
cost_matrix[row_ind, col_ind].sum()
。行索引将按排序;如果是方阵成本矩阵,它们将等于numpy.arange(cost_matrix.shape[0])
。
注释
线性总和分配问题 [1] 也称为二分图中的最小权重匹配问题。问题实例由矩阵 C 描述,其中每个 C[i,j] 是将第一个部分集合(“工人”)中的顶点 i 与第二个集合(“任务”)中的顶点 j 匹配的成本。目标是找到一个将工人完整分配给任务的最小成本方案。
形式上,令 X 为一个布尔矩阵,其中当且仅当行 i 分配给列 j 时 \(X[i,j] = 1\)。那么最优分配的成本为
\[\min \sum_i \sum_j C_{i,j} X_{i,j}\]其中,在矩阵 X 为方阵的情况下,每行恰好分配给一列,每列恰好分配给一行。
此函数还可以解决经典分配问题的推广,即成本矩阵为矩形。如果行数多于列数,则并非每行都需要分配给一列,反之亦然。
此实现是一种改进的 Jonker-Volgenant 算法,无初始化,在参考文献 [2] 中描述。
在版本 0.17.0 中添加。
参考文献
[2]DF Crouse. On implementing 2D rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems, 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