完全图的最大加权配对算法

Question

数学问题

让2n个人,C(i,j)让i和j一起工作的"成本" (函数C快速计算,在我的例子中它是一个给定的矩阵,并且是对称的).问题是找到2n对人的安排,最小化每对人的成本之和.

这应该在n中的多项式复杂度中完成,并且在Scilab语言中相对容易地实现(输入:成本矩阵,输出:配对,例如n -by-2索引矩阵).我知道"相对容易"需要解释......

以前的研究

这个问题实际上是由Blossom算法解决的.例如,参见本文.

然而,这个(及其变体)看起来像是一个噩梦.我真正的问题是n = 20,所以虽然蛮力(=尝试所有可能的配对)不行(暴力强迫n = 8花了一个小时在我的电脑上),几乎任何比蛮力更好的应该做的伎俩; 如果我能以一小时的计算成本避免一周的编码.

我正在考虑在2n- by- 2n阵列上使用匈牙利/ Munkres算法,用对称成本矩阵填充对角线和其他元素,然后以某种方式从结果置换中选择相关的配对,但我找不到一个可靠的方法来做到这一点.(注意,匈牙利语算法已经编码为单独的部分,因此您可以免费使用它来实现"易于实现"的要求.)+%inf

我希望与开花算法问题相比,图的完整性允许一些捷径...... (编辑:请参阅下面的DE评论,由于半明显的原因,这是错误的)

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 算法。