1

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

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

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

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

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

4

1 回答 1

2

这是一篇论文,声称给出了一种算法,可以在最佳时间和空间内枚举所有稳定的婚姻。作者 Dan Gusield 是一位非常有声望的计算机科学家,因此几乎可以肯定它是正确的。

于 2014-04-07T15:35:35.383 回答