问题标签 [stable-marriage]

据我了解，只要图表完整，SMP 总会有一个稳定的解决方案。换句话说，每个男性都可以娶每个女性，反之亦然。

但是，如果这不成立呢？可以说，有些男性有一份在任何情况下都不能结婚的女性名单。

这是另一个问题还是存在解决这个问题的好算法。这个问题不应该总是有我认为的解决方案，但我想得到一个尽可能好的解决方案。

每个稳定的婚姻问题都至少有一个解决方案。但是，如何知道稳定婚姻问题的最大解决方案数？Gale-Shapley 算法只能找到一种人最优解。如果我们使用女性最优方法来运行 Gale-Shapley，可能还有另一种解决方案。一个稳定婚姻的例子最多有两个解决方案，还是盖尔-沙普利只能找到两个解决方案，除此之外还有其他一些解决方案？

我一直在为我所在的课程研究“稳定的婚姻问题”，但我无法正确实施 Gale-Shapely 算法。提示时输出：

是“布赖恩·帕特里夏·乔治·南希·约翰·苏珊·罗伯特·南希·斯蒂芬·乔伊斯”，只是他们都在不同的路线上。如何正确的组合是“布莱恩·帕特里夏·乔治·乔伊斯·约翰·苏珊·罗伯特·南希·斯蒂芬·安妮”。问题是它不会删除“南希”作为乔治的一对。同样对于背景男性[][] 是男性偏好的矩阵格式 men[i][0] 是 0 < i < 4 和 men[i][k] 的每个男人的姓名，其中 k 作为位置 1 < k < 5 的首选项。对于 women 矩阵也是如此。还有Couples[] 是对象 "couple" 的数组，它基本上是一个数组，其中包含每对匹配的男人和女人。这里是问题所在：

想象一下它是公元前 3000 年，我们正在建立一些异性恋、一夫多妻制的快速约会。有n_c男有n_s女（n_s > n_c）。快速约会将分n_r轮进行。在每一轮中，每个男人都会遇到一个女人。所以n_r*n_c插槽要填补。

此外，他们都填写了石碑问卷，我们从中构建了一个评分函数 ， 它给出了在其中一个插槽u(i,j)中配对男人i和女人的效用。j

目标是最大化所有时段的得分总和，在此约束条件下，没有男人会遇到同一个女人超过一次，并且每个女人最多会遇到 ceil(n_r*n_c/n_s) 男人。（也就是说，每个女人应该与大约相同数量的男人见面。）

你能画出一个算法来解决这个问题吗？可以假设男性和女性的数量在 100 人以下，可能在 50 人以下。哦，假设我们将现代硬件带到了公元前 3000 年。

我正在编写一个算法来匹配不同群体的学生。每组名额有限。每个学生提供他们的前 5 组选择。然后将学生按预定顺序分组（年龄较大的学生和出勤率高的学生被优先考虑）。没有要求完全填充组，但不能填充通过容量。

我研究过类似的婚姻问题，例如 Gale-Shapely 稳定婚姻算法，但我遇到的问题是组比学生少得多，每个组可以接受多个学生。

实现这种算法以找到完全优化的解决方案的最佳方法是什么，使得学生分组没有更好的安排？在算法复杂度方面，我将大约 600 名学生分成 10-20 个小组。

我正在寻找解决以下问题的算法：

• 给定：一组项目及其相似度矩阵。
• 目标：将这些项目分组到最小大小为m的“集群”中
• 条件：
  • 数据集中没有类簇结构， 如图1
  • 无论如何，组中的项目应该彼此相似。因此，全局相似性会很高。

动机不是识别好的集群，而是将数据集分成高相似性和最小大小的组。围绕 medoids 进行分区并不是开箱即用的，它会产生很多 1-item-clusters。分层方法（AGNES、DIANA）也无济于事。

这个问题在某种程度上类似于稳定婚姻问题：尝试通过相似性对相邻项目进行排名。但在这里，一组/一婚至少有m个物品。

提前致谢！

我正在阅读稳定的婚姻问题，偶然发现了这个问题：一个男人1的偏好列表中有没有女人1，女人1的偏好列表中有男人1，但仍然存在稳定的匹配（不一定男人最佳或女人最佳）他们没有配对在一起？

给出了以下算法：我们选择一个初始分配的 man^woman，以便每个男人都与一个女人订婚，反之亦然。现在，如果有一个男人 m 更喜欢女人 f' 而不是他的实际伴侣 f，而一个女人 f 更喜欢男人 m 而不是她的实际伴侣 m'，那么 m 和 f 订婚，m' 和 f' 订婚。重复此操作，直到没有变化发生。现在我正在寻找一个有 3 男 3 女永无止境的案件。每个男人和女人的偏好必须是什么才能使算法永无止境？谢谢你的时间！

我正在尝试实现一种算法，以在没有 Gale-Shapley 算法的情况下使用蛮力方法找到所有稳定的婚姻解决方案（因为它只给了我们其中的 2 个）。我正在使用在rosettacoode中找到的检查机制，但我很难找到一种方法来创建所有可能的匹配而不重复（你有2个循环的那种），例如

UPDATE1： 到目前为止，所有解决方案都无法在它变大时运行它。我可能应该递归地做它而不存储长数据结构，当我得到它时测试单个结果并丢弃其他结果。我提出了这个解决方案，但仍然有问题，因为给了我一些重复和缺少的东西。我不知道如何解决它，对不起，我的大脑正在融化！

给我这个输出

更新 2 我受@Zags 启发的完整工作练习（受@Jonas 启发）：

输出正确：

我对稳定婚姻问题的表述略有不同。基本上，我可以将一个男人与一个女人匹配，但偏好列表不完整，这意味着一个男人只对一部分女性表达了兴趣，反之亦然。我认为原始的 Gale Shapley 算法不适用于此，如果可以，我需要进行哪些修改？如果 Gale Shapely 在这里不起作用，有什么算法可以解决这个问题吗？非常欢迎代码建议，特别是在 python 中针对此类问题。

更具体地说，这就是问题所在：

喜好：

男士：

女性：

我需要将每个男人与一个且只有一个女人匹配，并且允许的偏好数量是固定的，并且少于候选人的数量。