每个稳定的婚姻问题都至少有一个解决方案。但是，如何知道稳定婚姻问题的最大解决方案数？Gale-Shapley 算法只能找到一种人最优解。如果我们使用女性最优方法来运行 Gale-Shapley，可能还有另一种解决方案。一个稳定婚姻的例子最多有两个解决方案，还是盖尔-沙普利只能找到两个解决方案，除此之外还有其他一些解决方案？
问问题
2694 次
1 回答
2
请参阅https://cstheory.stackexchange.com/questions/5619/what-is-the-maximum-number-of-stable-marriages-for-an-instance-of-the-stable-mar讨论了一个给出了 n 男/女的所有 n 的 Omega(2.28^n) 稳定婚姻的指数最坏情况下限（通过给出一系列可能有这么多稳定婚姻的例子）。
于 2014-09-02T23:18:05.637 回答