Ctrl+K
scipy.optimize.

linear_sum_assignment#

scipy.optimize.linear_sum_assignment()#

解決線性總和分配問題。

參數:
cost_matrix陣列

二分圖的成本矩陣。

maximizebool (預設值：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 版本中新增。

參考文獻

[2]

DF Crouse. On implementing 2D rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems, 52(4):1679-1696, August 2016, 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
本頁面