algorithm - 多项式时间用户配对算法

Question

我有一个问题。考虑具有不同权重的用户，这取决于当前 channel 。即如果 channel 好，权重就高。我必须以系统总重量最大的方式对用户进行配对。我会详细说明这一点。考虑 4 个 channel 和 8 个用户，现在我必须将配对的用户放在每个 channel 中，以使权重总和最大并且所有用户都将配对。请建议一些多项式时间算法，而不是最优(蛮力)，当用户数量很大时会变得复杂，这对我有很大帮助。

感谢和问候，斯里努。

Answer 1

Vladimir Kolmogorov 发表 Blossom V: a new implementation of a minimum costperfect matching algorithm在 2009 年为“计算无向加权图中最小成本的完美匹配问题”提供了多项式算法。

通过更改权重的符号来更改为最大成本是微不足道的。

该算法的最坏情况复杂度为 O(n^3m)(但对于典型示例而言通常要快得多)。 n 是节点数，m 是边数。在您的情况下，我相信所有 n^2 条边都存在，因此复杂度为 O(n^5)。

如果您的图表是二分的(例如，用户分为男性和女性两类，您必须始终将男性与女性匹配)，则算法会更快，但我认为您不是这种情况吗？

此算法的软件实现是 here .