穩定婚姻實例解決方案的最大數量是多少？

每個穩定婚姻問題至少有一個解決方案。然而，如何知道解決穩定婚姻問題的最大數量？ Gale-Shapley算法只能找到一個人爲最優解。如果我們使用女性最佳方法來運行Gale-Shapley，那麼可能有另一種解決方案。一個穩定婚姻的例子最多有兩個解決方案嗎？或者Gale-Shapley只能找到兩種解決方案，除此之外還有其他一些解決方案。穩定婚姻實例解決方案的最大數量是多少？

感謝您的任何幫助答案！

來源

2014-09-02 microbit

肯定可以有兩種以上的解決方案。 [維基百科文章]（http://en.wikipedia.org/wiki/Stable_marriage_problem）給出了三個解決方案的例子。 – 2014-09-02 22:17:49

如果這不是＃P完全問題，我會感到有點驚訝。 – 2014-09-02 22:26:20

@DavidEisenstat您的懷疑是正確的：[計數穩定婚姻的複雜性]（http://epubs.siam.org/doi/abs/10.1137/0215048），SIAM J. Comput。，15（3），655-667 – mhum 2014-09-02 22:48:42

見https://cstheory.stackexchange.com/questions/5619/what-is-the-maximum-number-of-stable-marriages-for-an-instance-of-the-stable-mar在那裏討論了指數最壞情況下的下界歐米茄（2.28^n）的穩定婚姻，給出了所有用於n男性/女性（通過給一個家庭的例子，其中這麼多穩定的婚姻是可能）。

來源

2014-09-02 23:18:05 user2566092

穩定婚姻實例解決方案的最大數量是多少？

回答

相關問題