12

有什么好的算法可以解决这个问题？

我有三组人——A组、B组和C组。每组的人数相同。他们每个人都有一个他们愿意与之合作的其他组中的人员列表。我想将所有这些人分成 3 人一组（一个来自 A，一个来自 B，一个来自 C），这样一个组中的每个人都希望与他们组中的其他人一起工作。

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

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

4

6 回答 6

19

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

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

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 部​​分匹配问题的非最佳解决方案，请参见本文：

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

于 2008-11-17T01:00:17.003 回答
10

这与稳定婚姻问题的扩展不同，因为据我了解 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

于 2008-11-17T05:52:03.230 回答
2

只是对这个问题的快速说明。首先，它不是稳定婚姻问题的一个例子，实际上也不是它的延伸（即3D稳定匹配问题）。无论如何，这是一个已知为 NP-hard 的 3D 匹配问题（参见 Garey 和 Johnson）。要以合理的方式解决此类问题，您可能需要使用某种形式的约束、整数或线性规划（存在其他方法）。可能有用的是新的 Microsoft Solver Foundation，因此请检查一下。

于 2009-02-11T15:43:04.043 回答
0

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

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

于 2008-11-18T09:31:07.283 回答
0

我遇到了一个类似的问题，只是写了一个暴力破解它的脚本...... http://grouper.owoga.com/

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

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

于 2016-09-15T05:12:34.843 回答
0

可能，以下文章可以帮助您：https ://en.wikipedia.org/wiki/Lattice_of_stable_matchings

在其最简单的形式中，稳定匹配问题的一个实例由两组相同数量的要相互匹配的元素组成，例如医生和医院的职位。每个元素对其他类型的元素都有一个偏好顺序：每个医生对他们想在哪家医院工作有不同的偏好（例如，基于他们更喜欢住在哪个城市），每个医院都有自己的偏好他们愿意为哪些医生工作（例如基于专业或推荐）。目标是找到一个稳定的匹配：没有一对医生和医院比他们指定的匹配更喜欢对方。例如，国家居民匹配计划使用这个问题的版本来匹配美国医学生与医院。

一般来说，可能有许多不同的稳定匹配。例如，假设有三个医生（A、B、C）和三个医院（X、Y、Z），他们的偏好是：

A: YXZ   B: ZYX   C: XZY  
X: BAC   Y: CBA   Z: ACB

这种匹配安排有三种稳定的解决方案：

  • 医生有他们的第一选择，医院有他们的第三选择：AY、BZ、CX。
  • 所有参与者都有第二个选择：AX、BY、CZ。
  • 医院是他们的第一选择，医生是他们的第三选择：AZ、BX、CY。

对于任何稳定匹配的实例，稳定匹配的格组织了这个解决方案的集合，使其具有分布格的结构。

于 2021-05-04T20:09:51.537 回答