让2n个人,C(i,j)让i和j一起工作的"成本" (函数C快速计算,在我的例子中它是一个给定的矩阵,并且是对称的).问题是找到2n对人的安排,最小化每对人的成本之和.
这应该在n中的多项式复杂度中完成,并且在Scilab语言中相对容易地实现(输入:成本矩阵,输出:配对,例如n -by-2索引矩阵).我知道"相对容易"需要解释......
这个问题实际上是由Blossom算法解决的.例如,参见本文.
然而,这个(及其变体)看起来像是一个噩梦.我真正的问题是n = 20,所以虽然蛮力(=尝试所有可能的配对)不行(暴力强迫n = 8花了一个小时在我的电脑上),几乎任何比蛮力更好的应该做的伎俩; 如果我能以一小时的计算成本避免一周的编码.
我正在考虑在2n- by- 2n阵列上使用匈牙利/ Munkres算法,用对称成本矩阵填充对角线和其他元素,然后以某种方式从结果置换中选择相关的配对,但我找不到一个可靠的方法来做到这一点.(注意,匈牙利语算法已经编码为单独的部分,因此您可以免费使用它来实现"易于实现"的要求.)+%inf
我希望与开花算法问题相比,图的完整性允许一些捷径...... (编辑:请参阅下面的DE评论,由于半明显的原因,这是错误的)