查看“︁穩定婚姻問題”︁的源代码

在[[組合數學]]、[[經濟學]]、[[電腦科學]]中，'''穩定婚姻問題'''（{{lang-en|stable marriage problem}}，簡稱'''SMP'''）又稱為'''穩定配對問題'''（stable matching problem），是指在兩組同樣大小的[[元素 (數學)|元素]][[集合 (數學)|集合]]中（例如集合1是男子組、集合2是女子組，而他們各有偏好），尋求一個穩定配對組合所遇到的問題。一個組合在以下情況下並不穩定：

在集合1中有一個元素A更偏好於集合2的一些元素B，但元素A已被配對；而元素B亦更偏好於元素A多於配對給他的元素。在男女婚姻的角度來說，可以寫成一名男子A獲安排與女子D結婚，但A實際上是更喜歡女子B的。反之，女子B亦被安排與男子C結婚，但B實際上也是更喜歡A的。

簡單來說，一個穩定的組合是指在任何一個組合中（含A及B），每一個元素都是最偏好目前的組合多於任何其他的元素。亦即是說，穩定婚姻配對是指在同等數量男女當中，每一名男子皆能與自己最喜歡的女子結婚，反之亦然。然而，這個配對方式卻引來不少難題。

== 解決辦法 ==

1962年David Gale和Lloyd Shapley提出了[[盖尔-沙普利算法]]，這個系統可以確保如果男子組跟女子組的成員數皆相同（即N男N女）中，每一名男子和女子都能找到一名伴侶，以及每個婚姻都是穩定的。<ref>{{cite journal |first=D. |last=Gale |first2=L. S. |last2=Shapley |title=College Admissions and the Stability of Marriage |journal=[[American Mathematical Monthly]] |volume=69 |issue=1 |pages=9–14 |year=1962 |jstor=2312726 |doi=10.2307/2312726 |url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0251958 |access-date=2019-09-07 |archive-date=2017-09-25 |archive-url=https://web.archive.org/web/20170925172517/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0251958 }}</ref><ref>[[Harry Mairson]]: "The Stable Marriage Problem", ''The Brandeis Review'' 12, 1992 ([http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html online] {{Wayback|url=http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html |date=20110927025812 }}).</ref>

假設在n男n女中的存在兩對夫婦(M, W)和(m, w)，M男對w女喜好度大於現任妻子W女，並且w女對M男喜好度也大於現任丈夫m男：
 -{}-'''函數''' 穩定婚姻 {
     初始所有 ''m'' <math>\in</math> M 與 ''w'' <math>\in</math> W 為 ''單身''
     '''當''' <math>\exists</math> ''單身'' 男子 ''m'' {
        w = m 是所有可考慮的女子中排名最高的
        '''若''' w 是 ''單身''
          撮合 (m, w)
        '''否則''' 有些夫婦 (m', w) 存在
          '''若''' w 喜歡 m 多於 m'
            (m, w) 為 ''夫婦''
            m' 為 ''單身''
          '''否則'''
            (m', w) 仍為 ''夫婦''
     }
 }

== 參見 ==
* [[任務分配問題]]

==參考==
{{REFLIST}}

== 外部連結 ==
* [https://web.archive.org/web/20160304194304/http://www.math.ntu.edu.tw/~gjchang/courses/2004-02-high-school-stud/SDR.doc 相異代表系面面觀]，張鎮華

{{Authority control}}

[[Category:組合數學]]
[[Category:博弈论]]
[[Category:數學問題]]