将首选合作伙伴匹配为三个一组的算法

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

我有三组人--A组,B组和C组.每组中有相同数量的人.他们每个人都有一份他们愿意与之合作的其他群体的人员名单.我希望将所有这些人组成3个小组(一个来自A,一个来自B,一个来自C),这样一个群体中的每个人都想与他们小组中的其他人一起工作.

我怎样才能快速找到这些群体？如果没有办法让每个人都开心,那么算法首先应该让尽可能多的团队有三个人想要彼此合作,然后让其他团队中的人多开心.

最后一点:人们同意他们想与谁合作(如果x人想与y合作,那么你也想与x合作).如果你还可以给你的算法运行时间大一点,那就太好了!

这就像稳定的婚姻问题,但有三方而不是两方.

查看以前的问题(双分图匹配)的有效解决方案,并根据您的需求进行调整.

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

一种适应可能是首先仅从A组和B组构建工作对.然后,这些对必须与来自C组的工人配对.让这对组只喜欢两个成员都同意的工人(给出他们的名单).请注意,这只会给出局部最优.

k-partite匹配的最优解是NP难以找到:

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

有关k-partite匹配问题的非最优解决方案,请参阅此文章:

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的最优解.

这与稳定的婚姻问题的延伸不同,因为据我所知,OP的问题是,每个群体中的人都没有从最多到最少的人有序合作的清单; 这是一种二元关系(愿意/不愿意).

这可以表示为可以非常快速地解决的整数编程问题.我给出了下面问题的数学公式; 您可以使用像glpk或AMPL/CPLEX这样的包来处理数据.

定义以下矩阵:

M1 = |A| x |B| 矩阵,在哪里

M1(a,b) = 1 如果a(给定的A成员)愿意使用b(给定B成员),否则为0

M2 = |A| x |C|矩阵,M2(a,c) = 1如果a(给定的A成员)愿意使用c(给定的C成员),则为0,否则为0

M2 = |B| x |C| 矩阵,在哪里

M3(b,c) = 1 如果b(给定B成员)愿意使用c(给定C成员),则为0

现在定义一个我们将用于最大化的新矩阵:

X = |A| x |B| x |C| 矩阵,在哪里

X(a,b,c) = 1 如果我们让a,b和c一起工作.

现在,定义我们的目标函数:

//最大化组数

最大化 Sum[(all a, all b, all c) X(a,b,c)]

受以下限制:

//确保没有人被分成两组

对于a的所有值: Sum[(all j, k) X(a, j, k)] <= 1

对于b的所有值: Sum[(all i, k) X(i, b, k)] <= 1

对于c的所有值: Sum[(all i, j) X(i, j, c)] <= 1

//确保所有组都由兼容的个人组成

对于所有a,b,c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3