What's a good algorithm to solve this problem?
什么是解决这个问题的好算法?
I have three groups of people - group A, group B, and group C. There are the same number of people in each group. They each have a list of people in the other groups that they're willing to work with. I want to group all these people together in groups of 3 (one from A, one from B, and one from C) such that everyone in a group wants to work with the other people in their group.
我有三组人--A组,B组和C组。每组中有相同数量的人。他们每个人都有一份他们愿意与之合作的其他团体的人员名单。我想将所有这些人组成3人一组(一组来自A,一组来自B,一组来自C),这样一个小组中的每个人都想与小组中的其他人一起工作。
How can I find these groups in a fast way? If there's no way to make everyone happy, then the algorithm should first make as many groups have three people who want to work with each other, and then make as many people in the other groups happy.
我怎样才能快速找到这些群体?如果没有办法让每个人都开心,那么算法首先应该让尽可能多的团队有三个人想要彼此合作,然后让其他团队中的其他人快乐。
One final point: people agree on who they want to work with (if person x wants to work with person y, then y also wants to work with x). If you could also give a big-O of the running time of your algorithm, that'd be great!
最后一点:人们就他们想要合作的人达成一致意见(如果x人希望与y合作,那么你也想与x合作)。如果你还可以给你的算法运行时间大一点,那就太好了!
5 个解决方案
#1
18
This is like the stable marriage problem, but with 3 parties instead of two.
这就像稳定的婚姻问题,但有三方而不是两方。
Have a look at efficient solutions for former problem (bi-partite graph matching) and adapt them to your needs.
查看以前问题的有效解决方案(双分图匹配)并根据您的需求进行调整。
http://en.wikipedia.org/wiki/Stable_marriage_problem
One adaptation could be to first build working pairs from groups A and B only. Then these pairs have to be paired with a worker from group C each. Let the pairs only prefer workers which both members of the pair agree on (given their lists). Note that this will only give a local optimum.
一种适应可能是首先仅从A组和B组构建工作对。然后,这些对必须与来自C组的工人配对。让这对组只喜欢两个成员都同意的工人(给出他们的名单)。请注意,这只会给出局部最优。
An optimal solution to k-partite matching is NP-hard to find:
k-partite匹配的最优解是NP难以找到:
http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps
See this paper for a non-optimal solution to the k-partite matching problem:
有关k-partite匹配问题的非最优解决方案,请参阅此文章:
I'm sure you can find others on Google yourself now that you know the terms to search for. I don't know if there is an efficient algorithm giving the optimal solution for k=3.
我相信你现在知道要搜索的条款,你可以自己在Google上找到其他人。我不知道是否有一种有效的算法给出k = 3的最优解。
#2
10
This is different from an extension of the stable marriage problem, since as I understand the OP's question, the people in each group do not have an ordered list of who they want to work with from most to least; it's a binary relationship (willing/not willing).
这与稳定婚姻问题的延伸不同,因为据我所知,OP的问题是,每个群体中的人都没有从大多数情况到最不需要与他们合作的人的有序列表;这是一种二元关系(愿意/不愿意)。
This can be formulated as an integer programming problem that can be solved quite quickly. I give the mathematical formulation of the problem below; you can use a package like glpk or AMPL/CPLEX to process the data.
这可以表示为可以非常快速地解决的整数编程问题。我给出了下面问题的数学公式;您可以使用像glpk或AMPL / CPLEX这样的包来处理数据。
Define the following matrices:
定义以下矩阵:
M1 = |A| x |B| matrix, where
M1 = | A | x | B |矩阵,在哪里
M1(a,b) = 1 if a (given member of A) is willing to work with b (given member of B), and 0 otherwise
如果a(给定的A成员)愿意使用b(给定B成员),则M1(a,b)= 1,否则为0
M2 = |A| x |C| matrix, where M2(a,c) = 1 if a (given member of A) is willing to work with c (given member of C), and 0 otherwise
M2 = | A | x | C |矩阵,其中M2(a,c)= 1,如果a(给定的A成员)愿意使用c(给定的C成员),否则为0
M2 = |B| x |C| matrix, where
M2 = | B | x | C |矩阵,在哪里
M3(b,c) = 1 if b (given member of B) is willing to work with c (given member of C), and 0 otherwise
如果b(B的给定成员)愿意使用c(给定的C成员),则M3(b,c)= 1,否则为0
Now define a new matrix we will use for our maximization:
现在定义一个我们将用于最大化的新矩阵:
X = |A| x |B| x |C| matrix, where
X = | A | x | B | x | C |矩阵,在哪里
X(a,b,c) = 1 if we make a, b, and c work together.
如果我们使a,b和c一起工作,则X(a,b,c)= 1。
Now, define our objective function:
现在,定义我们的目标函数:
//Maximize the number of groups
//最大化组数
maximize Sum[(all a, all b, all c) X(a,b,c)]
最大化Sum [(全部a,全部b,全部c)X(a,b,c)]
subject to the following constraints:
受以下限制:
//To ensure that nobody gets placed in two groups
//确保没有人被分成两组
For all values of a: Sum[(all j, k) X(a, j, k)] <= 1
对于a的所有值:Sum [(all j,k)X(a,j,k)] <= 1
For all values of b: Sum[(all i, k) X(i, b, k)] <= 1
对于b的所有值:Sum [(all i,k)X(i,b,k)] <= 1
For all values of c: Sum[(all i, j) X(i, j, c)] <= 1
对于c的所有值:Sum [(all i,j)X(i,j,c)] <= 1
//To ensure that all groups are composed of compatible individuals
//确保所有组都由兼容的个人组成
For all a,b,c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
对于所有a,b,c:X(a,b,c)<= M1(a,b)/ 3 + M2(a,c)/ 3 + M3(b,c)/ 3
#3
2
Just a quick note to this problem. First, it is not an example of the stable marriage problem, nor in fact an extension of it (i.e. the 3D stable matching problem). Regardless though, it is a 3D matching problem which known to be NP-hard (see Garey and Johnson). To solve such a problem in a reasonable way, it is likely that you will need to use some form of constraint, integer, or linear programming (others methods exist). Something that might be of use is the new Microsoft Solver Foundation, so check it out.
只是快速记下这个问题。首先,它不是稳定婚姻问题的一个例子,实际上也不是它的延伸(即3D稳定匹配问题)。无论如何,这是一个3D匹配问题,已知是NP难的(参见Garey和Johnson)。要以合理的方式解决这个问题,您可能需要使用某种形式的约束,整数或线性编程(存在其他方法)。可能有用的东西是新的Microsoft Solver Foundation,所以请查看它。
#4
0
To start with, you can eliminate any facts where the two parties have disjoint lists of who they will work with in the third group. Then start a brute force, depth first search, always picking from least popular to most popular.
首先,您可以消除任何事实,即双方在第三组中将与谁合作的列表不相交。然后开始蛮力,深度优先搜索,总是从最不受欢迎到最受欢迎。
Alternatively, equivalent to the above elimination, form a list of all possible trios and work from that instead.
或者,等同于上述消除,形成所有可能的三重奏的列表并从中起作用。
#5
0
I ran into a similar problem and just wrote a script that brute-forces it... http://grouper.owoga.com/
我遇到了类似的问题,只是写了一个粗暴强制它的脚本...... http://grouper.owoga.com/
My initial thoughts were: for a larger group that was too large to brute force, some type of genetic algorithm? Make N random swaps M times. Score each new arrangement by some 'happiness' function. Take the best few, breed, repeat.
我最初的想法是:对于一个太大而不能暴力的大群体,某种类型的遗传算法?使N次随机交换M次。通过一些“幸福”功能对每个新安排进行评分。采取最好的几个,繁殖,重复。
For small groups I ended up getting better results by looping over a few groups, finding the 'best' swap (the one that produced the highest overall 'happiness' gain), making that, then repeating.
对于小团体,我最终通过循环几个小组获得更好的结果,找到“最佳”交换(产生最高整体'幸福'收益的交换),然后重复。
#1
18
This is like the stable marriage problem, but with 3 parties instead of two.
这就像稳定的婚姻问题,但有三方而不是两方。
Have a look at efficient solutions for former problem (bi-partite graph matching) and adapt them to your needs.
查看以前问题的有效解决方案(双分图匹配)并根据您的需求进行调整。
http://en.wikipedia.org/wiki/Stable_marriage_problem
One adaptation could be to first build working pairs from groups A and B only. Then these pairs have to be paired with a worker from group C each. Let the pairs only prefer workers which both members of the pair agree on (given their lists). Note that this will only give a local optimum.
一种适应可能是首先仅从A组和B组构建工作对。然后,这些对必须与来自C组的工人配对。让这对组只喜欢两个成员都同意的工人(给出他们的名单)。请注意,这只会给出局部最优。
An optimal solution to k-partite matching is NP-hard to find:
k-partite匹配的最优解是NP难以找到:
http://www.math.tau.ac.il/~safra/PapersAndTalks/k-DM.ps
See this paper for a non-optimal solution to the k-partite matching problem:
有关k-partite匹配问题的非最优解决方案,请参阅此文章:
I'm sure you can find others on Google yourself now that you know the terms to search for. I don't know if there is an efficient algorithm giving the optimal solution for k=3.
我相信你现在知道要搜索的条款,你可以自己在Google上找到其他人。我不知道是否有一种有效的算法给出k = 3的最优解。
#2
10
This is different from an extension of the stable marriage problem, since as I understand the OP's question, the people in each group do not have an ordered list of who they want to work with from most to least; it's a binary relationship (willing/not willing).
这与稳定婚姻问题的延伸不同,因为据我所知,OP的问题是,每个群体中的人都没有从大多数情况到最不需要与他们合作的人的有序列表;这是一种二元关系(愿意/不愿意)。
This can be formulated as an integer programming problem that can be solved quite quickly. I give the mathematical formulation of the problem below; you can use a package like glpk or AMPL/CPLEX to process the data.
这可以表示为可以非常快速地解决的整数编程问题。我给出了下面问题的数学公式;您可以使用像glpk或AMPL / CPLEX这样的包来处理数据。
Define the following matrices:
定义以下矩阵:
M1 = |A| x |B| matrix, where
M1 = | A | x | B |矩阵,在哪里
M1(a,b) = 1 if a (given member of A) is willing to work with b (given member of B), and 0 otherwise
如果a(给定的A成员)愿意使用b(给定B成员),则M1(a,b)= 1,否则为0
M2 = |A| x |C| matrix, where M2(a,c) = 1 if a (given member of A) is willing to work with c (given member of C), and 0 otherwise
M2 = | A | x | C |矩阵,其中M2(a,c)= 1,如果a(给定的A成员)愿意使用c(给定的C成员),否则为0
M2 = |B| x |C| matrix, where
M2 = | B | x | C |矩阵,在哪里
M3(b,c) = 1 if b (given member of B) is willing to work with c (given member of C), and 0 otherwise
如果b(B的给定成员)愿意使用c(给定的C成员),则M3(b,c)= 1,否则为0
Now define a new matrix we will use for our maximization:
现在定义一个我们将用于最大化的新矩阵:
X = |A| x |B| x |C| matrix, where
X = | A | x | B | x | C |矩阵,在哪里
X(a,b,c) = 1 if we make a, b, and c work together.
如果我们使a,b和c一起工作,则X(a,b,c)= 1。
Now, define our objective function:
现在,定义我们的目标函数:
//Maximize the number of groups
//最大化组数
maximize Sum[(all a, all b, all c) X(a,b,c)]
最大化Sum [(全部a,全部b,全部c)X(a,b,c)]
subject to the following constraints:
受以下限制:
//To ensure that nobody gets placed in two groups
//确保没有人被分成两组
For all values of a: Sum[(all j, k) X(a, j, k)] <= 1
对于a的所有值:Sum [(all j,k)X(a,j,k)] <= 1
For all values of b: Sum[(all i, k) X(i, b, k)] <= 1
对于b的所有值:Sum [(all i,k)X(i,b,k)] <= 1
For all values of c: Sum[(all i, j) X(i, j, c)] <= 1
对于c的所有值:Sum [(all i,j)X(i,j,c)] <= 1
//To ensure that all groups are composed of compatible individuals
//确保所有组都由兼容的个人组成
For all a,b,c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
对于所有a,b,c:X(a,b,c)<= M1(a,b)/ 3 + M2(a,c)/ 3 + M3(b,c)/ 3
#3
2
Just a quick note to this problem. First, it is not an example of the stable marriage problem, nor in fact an extension of it (i.e. the 3D stable matching problem). Regardless though, it is a 3D matching problem which known to be NP-hard (see Garey and Johnson). To solve such a problem in a reasonable way, it is likely that you will need to use some form of constraint, integer, or linear programming (others methods exist). Something that might be of use is the new Microsoft Solver Foundation, so check it out.
只是快速记下这个问题。首先,它不是稳定婚姻问题的一个例子,实际上也不是它的延伸(即3D稳定匹配问题)。无论如何,这是一个3D匹配问题,已知是NP难的(参见Garey和Johnson)。要以合理的方式解决这个问题,您可能需要使用某种形式的约束,整数或线性编程(存在其他方法)。可能有用的东西是新的Microsoft Solver Foundation,所以请查看它。
#4
0
To start with, you can eliminate any facts where the two parties have disjoint lists of who they will work with in the third group. Then start a brute force, depth first search, always picking from least popular to most popular.
首先,您可以消除任何事实,即双方在第三组中将与谁合作的列表不相交。然后开始蛮力,深度优先搜索,总是从最不受欢迎到最受欢迎。
Alternatively, equivalent to the above elimination, form a list of all possible trios and work from that instead.
或者,等同于上述消除,形成所有可能的三重奏的列表并从中起作用。
#5
0
I ran into a similar problem and just wrote a script that brute-forces it... http://grouper.owoga.com/
我遇到了类似的问题,只是写了一个粗暴强制它的脚本...... http://grouper.owoga.com/
My initial thoughts were: for a larger group that was too large to brute force, some type of genetic algorithm? Make N random swaps M times. Score each new arrangement by some 'happiness' function. Take the best few, breed, repeat.
我最初的想法是:对于一个太大而不能暴力的大群体,某种类型的遗传算法?使N次随机交换M次。通过一些“幸福”功能对每个新安排进行评分。采取最好的几个,繁殖,重复。
For small groups I ended up getting better results by looping over a few groups, finding the 'best' swap (the one that produced the highest overall 'happiness' gain), making that, then repeating.
对于小团体,我最终通过循环几个小组获得更好的结果,找到“最佳”交换(产生最高整体'幸福'收益的交换),然后重复。