完全图的最大权匹配算法

Question

数学问题

假设有2n个人，C(i,j)是让i和j一起工作的“成本”（函数C很快就能计算出来，在我的情况下它是一个给定的矩阵，并且是对称的）。问题是找到2n对人的安排，使每对人的成本之和最小。

这应该在n的多项式复杂度内完成，并且可以相对容易地在Scilab语言中实现（输入：成本矩阵，输出：配对，例如一个n-by-2的索引矩阵）。我知道“相对容易”是可以解释的...

以前的研究

这个问题实际上是由Blossom算法解决的。例如，参见这篇论文。

然而，这种方法（及其变体）看起来非常难以实现。我的真正问题是n=20，所以虽然暴力搜索（=尝试所有可能的配对）不可行（在我的电脑上暴力搜索n=8花了一个小时），但几乎任何比暴力搜索更好的方法都可以解决问题；如果我能避免一周的编程，代价是一小时的计算，那就太好了。

我考虑使用匈牙利/蒙克雷斯算法在2n-by-2n数组上进行操作，将对角线填充为+%inf，将其他元素填充为对称成本矩阵，然后从结果排列中选择相关的配对，但我无法找到可靠的方法来实现这一点。（注意，匈牙利算法已经编码为单独的部分，因此您可以在不影响“易于实现”要求的情况下使用它。）

我希望与开花算法问题相比，图的完整性允许一些捷径... （编辑：请参见DE的评论，由于某些半显然的原因，这是错误的）

- Leporello

---

G的完整性在一般情况下并不重要，因为某些边可能具有较高的权重，特别是对于Blossom算法来说更是如此，因为它是一种原始-对偶算法，并在紧密边子图上维护一般匹配。而匈牙利算法适用于二分图。要使其适用于一般图形并不容易修复，因为LP奇环约束条件非常复杂。 - David Eisenstat

Answer 1

很抱歉，我不熟悉Scilab，但如果您愿意使用Python，这将是非常容易的。因为Networkx库提供对此功能的支持。

import networkx as nx
import networkx.algorithms.matching as matching

def C(i,j):
    return i*j

n=40
G=nx.Graph()
for i in range(n):
    for j in range(n):
        G.add_edge(i,j,weight = -C(i,j))
M = matching.max_weight_matching(G,maxcardinality=True)
for i in M:
    print i,'with',M[i]

这段代码可以在一秒内输出答案。

函数C定义了将i和j配对的成本。请注意，权重设置为-C(i,j)，以便将max_weight_matching算法转换为min_weight_matching算法。

- Peter de Rivaz

---

我可以用Python来完成（它与此相当相似）。感谢您的指引。 - Leporello

权重可以为负数吗？ - Daniel

如果它们不允许为负数，您可以添加一个固定的偏移量到所有权重上，使它们变为正数。我相信networkx实现支持负权重。 - Peter de Rivaz