給定一組 
位男士和 
位女士，在每位男士按照偏好從 1 到 
對女士 
進行排序，並且每位女士也同樣對男士 
進行排序後，將他們配對結婚。如果最終的婚姻配對中不包含任何 形式為 
, 
的配對，使得 
相比 
更偏好 
，並且 
相比 
更偏好 
，則稱婚姻是穩定的。Gale 和 Shapley (1962) 證明了對於任何排名選擇，穩定婚姻都存在 (Skiena 1990, p. 245)。在美國，Gale 和 Shapley (1962) 的演算法被用於將醫院與實習醫生進行匹配 (Skiena 1990, p. 245)。
在上面圖示的排名中，男性最優穩定婚姻是 4, 2, 6, 5, 3, 1, 7, 9, 8，女性最優穩定婚姻是 1, 2, 8, 9, 3, 4, 7, 6, 5。可以使用以下方法找到穩定婚姻：StableMarriage[m, w] 在 Wolfram 語言 程式包中Combinatorica` .
另請參閱
離婚有向圖,
匹配
使用 探索
參考文獻
Gale, D. 和 Shapley, L. S. "College Admissions and the Stability of Marriage." Amer. Math. Monthly 69, 9-14, 1962.Gusfield, D. 和 Irving, R. W. The Stable Marriage Problem: Structure and Algorithms. Cambridge, MA: MIT Press, 1989.Skiena, S. "Stable Marriages." §6.4.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 245-246, 1990.
請引用本文為
Weisstein, Eric W. "穩定婚姻問題。" 來自 Web 資源。 https://mathworld.tw/StableMarriageProblem.html
主題分類
