minimum_weight_full_matching#
- minimum_weight_full_matching(G, top_nodes=None, weight='weight')[source]#
返回二分图
G的最小权重满匹配。设 \(G = ((U, V), E)\) 是一个加权二分图，其边权为实数 \(w : E \to \mathbb{R}\)。此函数产生一个匹配 \(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] 的说法，将此匹配称为 满 匹配。
- 参数:
- GNetworkX 图
无向二分图
- top_nodes容器
包含一个二分节点集中的所有节点的容器。如果未提供，则会计算。
- weight字符串, 可选 (默认值=’weight’)
用于提供矩阵中每个值的边数据键。如果为 None，则每条边的权重为 1。
- 返回:
- matches字典
匹配以字典形式返回，
matches，其中如果节点v与节点w匹配，则matches[v] == w。未匹配的节点不会出现在matches中作为键。
- 引发:
- ValueError
如果不存在满匹配，则引发此错误。
- ImportError
如果 SciPy 不可用，则引发此错误。
注意事项
确定最小权重满匹配的问题也称为矩形线性分配问题。此实现将分配的计算委托给 SciPy。
参考资料
[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.