min_weight_full_bipartite_matching#
- scipy.sparse.csgraph.min_weight_full_bipartite_matching(biadjacency, maximize=False)#
返回二分图的最小权重完全匹配。
在版本 1.6.0 中添加。
- 参数:
- biadjacency稀疏数组或矩阵
二分图的邻接矩阵:CSR、CSC 或 COO 格式的稀疏数组,其行表示图的一个分区,列表示另一个分区。两个顶点之间的边由矩阵中的相应条目指示,边的权重由该条目的值给出。这不应与图的完整邻接矩阵混淆,因为我们只需要定义二分结构的子矩阵。
- maximizebool (默认:False)
如果为 true,则计算最大权重匹配。
- 返回:
- row_ind, col_ind数组
行索引数组和相应的列索引数组,给出最佳匹配。匹配的总权重可以计算为
graph[row_ind, col_ind].sum()
。行索引将被排序;在方阵的情况下,它们将等于numpy.arange(graph.shape[0])
。
注释
设 \(G = ((U, V), E)\) 是一个具有非零权重 \(w : E \to \mathbb{R} \setminus \{0\}\) 的加权二分图。然后,此函数生成一个匹配 \(M \subseteq E\),其基数为
\[\lvert M \rvert = \min(\lvert U \rvert, \lvert V \rvert),\]这最小化了匹配中包含的边的权重之和,\(\sum_{e \in M} w(e)\),或者如果不存在这样的匹配,则引发错误。
当 \(\lvert U \rvert = \lvert V \rvert\) 时,这通常被称为完美匹配;在这里,由于我们允许 \(\lvert U \rvert\) 和 \(\lvert V \rvert\) 不同,我们遵循 Karp [1] 并将匹配称为完全。
此函数实现了 LAPJVsp 算法 [2],它是“线性分配问题,Jonker–Volgenant,稀疏”的缩写。
它解决的问题等同于矩形线性分配问题。 [3] 因此,此函数可用于解决与
scipy.optimize.linear_sum_assignment
相同的问题。当输入密集时,或者对于某些特定类型的输入(例如,其中 \((i, j)\)'th 条目是欧几里得空间中两点之间的距离),该函数可能表现更好。如果不存在完全匹配,此函数将引发
ValueError
。对于确定图中最大匹配的大小,请参见maximum_bipartite_matching
。我们要求权重仅为非零,以避免在不同稀疏表示之间转换时显式零的处理问题。零权重可以通过将常数添加到所有权重来处理,以便生成的矩阵不包含零。
如果存在多个有效解决方案,则输出可能随 SciPy 和 Python 版本而异。
参考文献
[1]Richard Manning Karp: An algorithm to Solve the m x n Assignment Problem in Expected Time O(mn log n). Networks, 10(2):143-152, 1980.
[2]Roy Jonker and Anton Volgenant: A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38:325-340, 1987.
示例
>>> from scipy.sparse import csr_array >>> from scipy.sparse.csgraph import min_weight_full_bipartite_matching
让我们首先考虑一个所有权重都相等的示例
>>> biadjacency = csr_array([[1, 1, 1], [1, 0, 0], [0, 1, 0]])
在这里,我们得到的只是图的完美匹配
>>> print(min_weight_full_bipartite_matching(biadjacency)[1]) [2 0 1]
也就是说,第一、第二和第三行分别与第三、第一和第二列匹配。请注意,在本示例中,输入矩阵中的 0 并不 对应于权重为 0 的边,而是对应于未通过边配对的一对顶点。
另请注意,在这种情况下,输出与应用
maximum_bipartite_matching
的结果匹配>>> from scipy.sparse.csgraph import maximum_bipartite_matching >>> biadjacency = csr_array([[1, 1, 1], [1, 0, 0], [0, 1, 0]]) >>> print(maximum_bipartite_matching(biadjacency, perm_type='column')) [2 0 1]
当有多个边可用时,首选权重最低的边
>>> biadjacency = csr_array([[3, 3, 6], [4, 3, 5], [10, 1, 8]]) >>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency) >>> print(col_ind) [0 2 1]
在这种情况下,总权重为 \(3 + 5 + 1 = 9\)
>>> print(biadjacency[row_ind, col_ind].sum()) 9
当矩阵不是正方形时,即当两个分区的基数不同时,匹配与两个分区中较小的分区一样大
>>> biadjacency = csr_array([[0, 1, 1], [0, 2, 3]]) >>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency) >>> print(row_ind, col_ind) [0 1] [2 1] >>> biadjacency = csr_array([[0, 1], [3, 1], [1, 4]]) >>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency) >>> print(row_ind, col_ind) [0 2] [1 0]
当一个或两个分区为空时,匹配也为空
>>> biadjacency = csr_array((2, 0)) >>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency) >>> print(row_ind, col_ind) [] []
通常,我们将始终达到与使用
scipy.optimize.linear_sum_assignment
时相同的权重之和,但请注意,对于该权重之和,丢失的边由float('inf')
的数组条目表示。让我们生成一个具有 1 到 10 之间的整数条目的随机稀疏数组>>> import numpy as np >>> from scipy.sparse import random_array >>> from scipy.optimize import linear_sum_assignment >>> sparse = random_array((10, 10), rng=42, density=.5, format='coo') * 10 >>> sparse.data = np.ceil(sparse.data) >>> dense = sparse.toarray() >>> dense = np.full(sparse.shape, np.inf) >>> dense[sparse.row, sparse.col] = sparse.data >>> sparse = sparse.tocsr() >>> row_ind, col_ind = linear_sum_assignment(dense) >>> print(dense[row_ind, col_ind].sum()) 25.0 >>> row_ind, col_ind = min_weight_full_bipartite_matching(sparse) >>> print(sparse[row_ind, col_ind].sum()) 25.0