问题标签 [stable-marriage]

问题陈述：

我们的男女人数相等。每个男人对每个女人都有一个偏好分数。每个男人的女人也是如此。每个男人和女人都有一定的兴趣。根据兴趣，我们计算偏好分数。

x所以最初，我们在一个有列的文件中有一个输入。第一列是人（男人/女人）ID。ID 只不过是来自0...的数字n。（上半场是男性，下半场是女性）。其余x-1列将有兴趣。这些也是整数。

现在，使用这个n by x-1矩阵，我们想出了一个n by n/2矩阵。新矩阵将所有男性和女性作为他们的行，并将异性的分数作为列。

我们必须对分数进行降序排序，还需要知道排序后与分数相关的人的id。

所以，在这里我想使用哈希表。

一旦我们得到分数，我们需要组成对，为此我们需要遵循一些规则。

我的麻烦在于第二个矩阵n by n/2需要提供关于哪个男人/女人对女人/男人有多少偏好的信息。我需要对这些分数进行排序，以便我知道谁是第一个喜欢的女人/男人，第二个喜欢男人/女人，依此类推。

我希望对我使用的数据结构有好的建议。我更喜欢 PHP 或 Perl。

注意：

这不是家庭作业。这是稳定婚姻算法的一个小修改版本。我有一个可行的解决方案。我只致力于优化我的代码。

它与稳定的婚姻问题非常相似，但在这里我们需要根据他们共同的兴趣来计算分数。所以，我已经按照您在 wiki 页面http://en.wikipedia.org/wiki/Stable_marriage_problem中看到的方式实现了它。

我的问题不是解决问题。我解决了它并且可以运行它。我只是想有一个更好的解决方案。所以我在询问要使用的数据结构类型的建议。

从概念上讲，我尝试使用哈希数组。其中数组索引给出人员 ID，其中的哈希给出ids <=> scores排序方式。我最初从一个哈希数组开始。现在，我对值的哈希值进行排序，但我无法将排序后的哈希值存储回数组中。因此，只需在排序后存储键并使用它们从我最初的未排序哈希中获取值。

我们可以在排序后存储哈希吗？你能推荐一个更好的结构吗？

我目前正在阅读一本算法的书，遇到了稳定匹配问题。我想到了一个我很好奇的问题，但这本书没有回答。在每个 SMP 中，是否总是有一对最喜欢另一对？就像在经典的婚姻例子中一样。是否总是有一对一女一男，并且彼此都在自己的偏好中排名靠前？

游戏Tiny Tower有各种 0-9 技能的“Bitizens”，具有不同的属性：

然后它就有了三个Bitizen可以从事的业务。每项业务都属于零售、创意、服务、娱乐和食品类别之一。企业数量或 Bitizen 数量之间永远不会有任何匹配，但为了让事情更容易，我们可以假设职位数量与 bitizen 数量相匹配。

例如，可能有一家零售业务的帽子店，因此具有高retail价值的Bitizen是有利的。在上面的例子中，迈克尔非常适合从事零售业务。

我怎样才能在算法上用最相关技能的Bitizen来填补职位？我试图解决这个问题，但我很难以一种实际上可以有效解决问题的方式绕开我的脑袋。

我想找到最佳匹配算法来重新创建经济模拟。

我将创建不同的客户群。每个组都有特定的参数，这些参数将决定客户想要购买什么。这些参数的示例：质量、功能、营销等。

我游戏中的每个玩家都会创建不同的产品并尝试满足不同客户群的需求。然后，他们将为每种产品定价，并决定他们将生产多少（数量有限）。

因此，一方面，您的客户数量有限。另一方面，您的产品数量有限。这些数量不需要相等（但可以）。因此，对于客户数量而言，您可能拥有过多的产品，或者对于产品数量而言，您可能拥有过多的客户。但有一件事是肯定的：每个客户都想购买一种产品，除非出现短缺。

我找到了稳定的 mariage 算法，但这个算法似乎并不完全适合我的情况。什么是最好的匹配算法？

这个问题与之前关于类似主题的帖子有关： 经济模拟算法？

我正在尝试找到一种算法来根据偏好将一组学生分成小组。每个学生选择三个他们想合作的学生和三个他们不想合作的学生。其余的被假定为“如有必要可以使用”。

找到最符合他们偏好的学生组合的最佳方法是什么？

所以我的问题是指什么是“稳定匹配”？我知道稳定婚姻问题，所有解决方案似乎都表明您以“稳定匹配”结束。但我不确定这实际上意味着什么。

我目前正在阅读一本算法书，遇到了稳定匹配问题。我想到了一个我很好奇的问题，但这本书没有回答。问题是：
对于任何匹配，如果它不稳定，则选择任何阻塞对（w，m），并匹配它们。并且还匹配他们以前的合作伙伴。并重复。这是达到稳定匹配的正确算法吗？
似乎答案是否定的。但我想不出一个反例。有没有人可以帮忙？

我需要在稳定的婚姻课程中实现 makeMatches 方法。代码需要遵循这个算法：

但是我找不到我的错误。该计划使夫妻依赖于他们的第一个选择，但之后不会继续并设置夫妻。你能看看我的代码并告诉我它有什么问题吗？

Person.java 由讲师提供：

StablaMarriage.java 是我需要在其中实现代码的那个。

以下问题来自 Jon Kleinberg 和 Éva Tardos 的“算法设计”，第 1 章，练习 3。我尽可能缩短了描述（我在括号中或引号之外的注释）

假设我们有两个电视网络，我们将调用它们A和B。有n黄金时段的节目时段，每个网络都有n电视节目。每个网络都想设计一个时间表——将每个节目分配到一个不同的时段——以便尽可能多地吸引市场份额。[...] 每个节目都有固定的收视率 [...]；我们假设没有两个节目的评分完全相同。如果一个网络为该时间段安排的节目比其他网络为该时间段安排的节目具有更大的收视率，则该网络赢得一个给定的时间段。目标是赢得尽可能多的时间段。

我们从每个网络得到一个赛季的时间表，所以第一个网络给我们一个时间表s，第二个网络给我们一个时间表T。

[...]如果两个网络都不能单方面改变自己的时间表并赢得更多时隙，我们会说这对时间表 (S, T) 是稳定的。

也就是说，没有S'可以给第一个网络更多时隙的时间表，也没有T'用于第二个网络的类似时间表。

【问题是】：每一套电视剧和收视率，总有一对稳定的档期吗？

我的直觉告诉我不，因为我能想象稳定时间表的唯一问题是当第一个网络的最佳节目仍然比第二个网络的最差节目差时，即当一个网络可以赢得所有时间表时. 否则，我认为一个网络可以交换两个条目以赢得更多的插槽，而另一个网络可以更改其时间表，以便它一直赢回这些插槽。

我有两个关于稳定婚姻问题的问题。

给定n个男人和n个女人，每个人按照优先顺序用一个介于1和n之间的唯一数字对所有异性成员进行排名，将男人和女人结婚，这样就没有两个异性会同时而不是拥有彼此而不是他们现在的合作伙伴。如果没有这样的人，所有的婚姻都是“稳定的”。

我从http://en.wikipedia.org/wiki/Stable_marriage_problem知道解决方案。wiki 页面解释了该解决方案，但没有解释该解决方案是如何引入的。

Q1：谁能给我解释一下这种配对问题是怎么想的？所以对于类似的问题我可以有一个思路。

Q2：如果我们想要所有可能的稳定婚姻组合怎么办？