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

Question

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

谢谢和问候，斯里努。

Answer 1

Vladimir Kolmogorov 在 2009 年发表了Blossom V：最小成本完美匹配算法的新实现，它为“在无向加权图中计算最小成本完美匹配的问题”提供了多项式算法。

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

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

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

该算法的软件实现在这里。