穩定婚姻問題

维基百科,自由的百科全书
跳转至: 导航搜索

組合數學穩定婚姻問題指:

有n男n女,每人都按他對(異性)對象的喜好程度按1至n排列。安排男女結婚,使得下列情形為真:

在n男n女中的任意兩對夫婦(M, W)和(m, w),都不存在

M男對w女喜好度大於現任妻子W女,並且w女對M男喜好度也大於現任丈夫m男

的情形發生,此種情形稱為不穩定

解法[编辑]

1962年Gale和Shapley提出一個演算法,對於每個系統,總能找到一個解決的辦法。

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

以上的例子是男子主動的,結果男子都儘可能得到他最想要的伴侶。

這個算法的應用包括大學聯合招生

參見[编辑]

外部連結[编辑]