1

情况：用户选择多个其他用户作为项目的可能合作伙伴。用户对他选择的一个用户没有偏好（即，他列表中的任何用户都足以成为合作伙伴）。例子：

| user_id | preferred_partners |
| 1       | 2 4                |
| 2       | 3 1                |
| 3       | 4 2 1              |
| 4       | 1                  |

真正的清单会大得多。

我的问题：给定一组用户及其首选合作伙伴（如上面的列表），我想生成一组最终合作对。最终合作对的数量必须最大化（我希望尽可能多的人成对）。

这是我认为我需要的算法：Edmonds's matching algorithm，但由于我不是数学背景，我在解释和实现它时遇到了麻烦。

任何帮助，将不胜感激。提前致谢。

4

2 回答 2

0

Edmonds 的算法可能是您想要的，但话又说回来，它可能不是。你会寻找三重奏吗？你会想要偏好的强度吗？您是否曾经想要一些关于您的机制的保证，例如，如果有人提出更多偏好，他们就不能从匹配变为不匹配？合作伙伴必须相互优先吗？如果不是，是否对共同偏好的合作伙伴有更多的重视？

其中一些变体可以通过 Edmonds 算法或其加权表亲来解决，该算法使用 Edmonds 来解决“受限原始”，其方式与匈牙利算法使用二分匹配算法的方式非常相似，但有些，特别是 3D 匹配，很难并且不适合可爱的组合算法。通过从 Ruby 中调用整数规划求解器，您可能会发现甚至可以更轻松地求解多时间情况。

于 2012-04-21T23:26:08.200 回答
0

Edmonds 的匹配算法确实是你想要的。这是一个很好的链接，提供了详细的解释

于 2012-04-21T22:51:06.357 回答