Gale-Shapley匹配结果不稳定是因为我的程序有bug还是说它不总是给出稳定匹配？
如果你是计算机专业的，你可能知道Gale-Shapley算法，很多算法老师都喜欢用它来向学生展示算法的乐趣。
算法就是基于这样一个前提，在一个完美的世界里，有N个男人和N个女人，他们就会结成N对情侣。每个男人和女人都有一个偏好的伙伴序列表，例如，Harry 的偏好伙伴列表是 Olivia、Emma、Julie 等。Emma 的男人名单是 Liem、Noah、Oliver 等，这个名单也可以长达 N。
Gale-Shapley 算法可以根据他们的偏好列表为所有 2N 人生成稳定匹配。规则是男人向女人求婚，如果她没有伴侣，她会说好让我们试试看，如果她有伴侣，她会比较这个求婚者M的排名和她现在的伴侣P的排名，如果M > P，那么她会接受新的伙伴M，然后放开她现在的伙伴P。这个过程有时候会进行几轮或迭代几次，最终为所有男性和女性产生稳定的匹配。稳定，这意味着每个人都会得到现实中可能得到的最好的伙伴。
我用一些随机的虚拟数据尝试了一下，但我发现有时我得到的结果往往有 1 对不稳定，就把他们叫做罗密欧与朱丽叶吧，他们都和别的人匹配，但是他们喜欢彼此的程度超过他们喜欢格子的伴侣，如果他们决定私奔，那整个匹配矩阵就可能崩溃。
我想请教一下，有没有精通该算法的人，这个算法不是“总能产生稳定的结果”吗？为什么我会发现罗密欧和朱丽叶，是不是我的程序有bug。我是菜鸟新手开发者，我也不是计算机科学背景，基本算是外行。
回答：
那么她会接受新的伙伴M，然后放开她现在的伙伴P
你的逻辑表达的不完整啊，然后怎么开始下一轮呢？
一种选择是下一步是让男生N求婚（N在M的下一顺位），依次循环，到了尾端之后再重新开始遍历，找到单身汪。
另一种选择是基于被释放的男生开始下一轮，（当然P又可能导致K被释放），直到本次求婚后没有人被释放才去让下一顺位的男生求婚。
当然还有其它方式。
第一次看到这个，也没太理解这种算法有什么乐趣，只是根据你的描述做一下推理而已。从你的描述上看你没有特别重视去定义怎么样才叫做完成一次匹配，也没有交代下次匹配开始的条件，这样来看bug的可能性会更大。
以上是 Gale-Shapley匹配结果不稳定是因为我的程序有bug还是说它不总是给出稳定匹配？ 的全部内容， 来源链接： utcz.com/p/938176.html
