穩定婚姻問題

在組合數學，穩定婚姻問題指：

有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) 仍為 夫婦
    }
}

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

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

參見

• 任務分配問題

外部連結

• 相異代表系面面觀，張鎮華