穩定婚姻問題
维基百科,自由的百科全书
在組合數學,穩定婚姻問題指:
- 有n男n女,每人都按他對(異性)對象的喜好程度按1至n排列。安排男女結婚,使得沒有一對不是夫婦的男女對對方的喜好程度都較被安排的配偶高(不穩定)。
[编辑] 解法
1962年Gale和Shapley提出一個演算法,對於每個系統,總能找到一個解決的辦法。
函數 穩定婚姻 { 初始所有 m M 與 w W 為 單身 當 單身 男子 m { w = m所有可考慮的女子中排名最高的 若 w 是 單身 撮合 (m, w) 否則 有些夫婦 (m', w) 存在 若 w 喜歡 m 更於 m' (m, w) 為 夫婦 m' 為 單身 否則 (m', w) 仍為 夫婦 } }
以上的例子是男子主動的,結果男子都盡可能得到他最想要的伴侶。
這個算法的應用包括大學聯合招生。
[编辑] 參見
[编辑] 外部連結
- 相異代表系面面觀,張鎮華