穩定婚姻問題

在組合數學、經濟學、電腦科學中，穩定婚姻問題（英語：，簡稱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提出了Gale–Shapley演算法，這個系統可以確保如果男子組跟女子組的成員數皆相同（即N男N女）中，每一名男子和女子都能找到一名伴侶，以及每個婚姻都是穩定的。[1][2]

假設在n男n女中的存在兩對夫婦(M, W)和(m, w)，M男對w女喜好度大於現任妻子W女，並且w女對M男喜好度也大於現任丈夫m男：

函數 穩定婚姻 {
    初始所有 m  M 與 w  W 為 單身
    當  單身 男子 m {
       w = m 是所有可考慮的女子中排名最高的
       若 w 是 單身
         撮合 (m, w)
       否則 有些夫婦 (m', w) 存在
         若 w 喜歡 m 多於 m'
           (m, w) 為 夫婦
           m' 為 單身
         否則
           (m', w) 仍為 夫婦
    }
}

參見
  • 任務分配問題

參考
  1. Gale, D.; Shapley, L. S. . American Mathematical Monthly. 1962, 69 (1): 9–14. JSTOR 2312726. doi:10.2307/2312726.
  2. Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online 页面存档备份，存于).

外部連結
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.