将首选合作伙伴分成三组的算法

Question

什么是解决这个问题的好算法？

我有三组人——A组、B组和C组。每组人数相同。他们每个人都有一份他们愿意合作的其他小组的人员名单。我想将所有这些人分成 3 人一组(一个来自 A，一个来自 B，一个来自 C)，这样一个组中的每个人都想与他们组中的其他人一起工作。

如何快速找到这些群组？如果没有办法让每个人都开心，那么算法应该首先让尽可能多的组中有三个人想要一起工作，然后让其他组中尽可能多的人开心。

最后一点:人们就他们想和谁一起工作达成一致(如果 x 想和 y 一起工作，那么 y 也想和 x 一起工作)。如果您还可以给出算法运行时间的大 O，那就太好了!

Answer 1

这就像稳定的婚姻问题，但有 3 方而不是两方。

查看前一个问题(二分图匹配)的有效解决方案，并根据您的需要进行调整。

http://en.wikipedia.org/wiki/Stable_marriage_problem

一种调整可能是首先仅从 A 组和 B 组构建工作对。然后这些对必须与 C 组中的每个 worker 配对。让两人只喜欢两人都同意的 worker (给定他们的名单)。请注意，这只会给出局部最优值。

k-partite 匹配的最优解是 NP-hard to find:

http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps

有关 k 部​​分匹配问题的非最优解，请参阅本文:

http://books.google.com/books?id=wqs31L1MF4IC&pg=PA309&lpg=PA309&dq=k-partite+matching&source=bl&ots=kgBuvi7ym_&sig=j3Y-nyo51y8qp0-HwToyUlkao4A&hl=de&sa=X&oi=book_result&resnum=1&ct=result

既然您知道要搜索的术语，我相信您可以自己在 Google 上找到其他人。我不知道是否有一个有效的算法给出 k=3 的最优解。