穩定婚姻問題

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

組合數學穩定婚姻問題(或穩定配對問題)指:

給定n男n女,以及每個人對異性對象的喜好程度(按1至n排列)。安排男女結婚,使得不出現以下不穩定情形:

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

解法[编辑]

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

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

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

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

參見[编辑]

外部連結[编辑]