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

Question

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

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

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

最后一点：人们就他们想与谁合作达成一致意见（如果x人想与y合作，那么你也想与x合作）。如果您还可以给出算法运行时间的大部分，那就太棒了！

Answer 1

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

查看以前问题的有效解决方案（双方图匹配）并根据您的需求进行调整。

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

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

k-partite匹配的最佳解决方案是NP难以找到：

http://www.math.tau.ac .il内/〜萨夫拉/ PapersAndTalks / k-DM.ps

参见本文，了解k-partite匹配问题的非最优解：

Answer 2

这与稳定婚姻问题的延伸不同，因为据我所知，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

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

快速记下这个问题。首先，它不是稳定婚姻问题的一个例子，实际上也不是它的延伸（即3D稳定匹配问题）。无论如何，这是一个3D匹配问题，已知是NP难的（见Garey和Johnson）。要以合理的方式解决这个问题，您可能需要使用某种形式的约束，整数或线性编程（存在其他方法）。可能有用的东西是新的Microsoft Solver Foundation，所以请查看它。

首先，您可以消除任何事实，即双方在第三组中将与谁合作的列表不相交。然后开始蛮力，深度优先搜索，总是从最不受欢迎到最受欢迎。

或者，等同于上述消除，形成所有可能的三重奏的列表并从中起作用。

我遇到了类似的问题，只是写了一个剧烈强制它的脚本...... http：// grouper。 owoga.com/

我最初的想法是：对于一个太大而无法暴力的大群体，某种类型的遗传算法？使N次随机交换M次。通过一些“幸福”功能对每个新安排进行评分。采取最好的几个，繁殖，重复。

对于小团体，我最终通过循环几个小组获得更好的结果，找到“最佳”交换（产生最高整体'幸福'收益的交换），然后重复。

Answer 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

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

Answer 4

快速记下这个问题。首先，它不是稳定婚姻问题的一个例子，实际上也不是它的延伸（即3D稳定匹配问题）。无论如何，这是一个3D匹配问题，已知是NP难的（见Garey和Johnson）。要以合理的方式解决这个问题，您可能需要使用某种形式的约束，整数或线性编程（存在其他方法）。可能有用的东西是新的Microsoft Solver Foundation，所以请查看它。

Answer 5

首先，您可以消除任何事实，即双方在第三组中将与谁合作的列表不相交。然后开始蛮力，深度优先搜索，总是从最不受欢迎到最受欢迎。

或者，等同于上述消除，形成所有可能的三重奏的列表并从中起作用。

Answer 6

我遇到了类似的问题，只是写了一个剧烈强制它的脚本...... http：// grouper。 owoga.com/

我最初的想法是：对于一个太大而无法暴力的大群体，某种类型的遗传算法？使N次随机交换M次。通过一些“幸福”功能对每个新安排进行评分。采取最好的几个，繁殖，重复。

对于小团体，我最终通过循环几个小组获得更好的结果，找到“最佳”交换（产生最高整体'幸福'收益的交换），然后重复。