作者ggg12345 (ggg)
看板AfterPhD
標題夏普利的匹配理論與台灣的入學分配(1)
時間Sat Aug 27 00:09:15 2016
https://www.youtube.com/watch?v=q4d7fNjCQ4A
這是 BBC 影片在 youtube 的放映本.
關於 stable matching 的實例, 片中是橋牌的 Queen 與 King 為例.
紅磚Queen 對 King(磚 桃 梅 黑桃) 的喜愛次序是 (3 4 2 1)
紅桃King 對 Queen(磚 桃 梅 黑桃) 的喜愛次序是 (1 2 3 4)
K
磚 桃 梅 黑桃
Q 磚 3,2 4,1 2,2 1,1
桃 2,1 4,2 1,3 3,2
梅 3,4 4,3 2,1 1,3
黑 2,3 3,4 4,4 1,4
假設 Queen 先對 King 表白喜愛的志願, 結果 黑桃King 收到 3個第一志願,
但黑桃King有其對Queen的喜愛志願. 此時, 梅黑 2 Queen就被 磚Queen比下去
梅Queen只好改找第二志願(2,1)當第一志願, 就是改找梅King. 此時, 桃Queen
的第一志願, 因為梅King 的志願喜好恰為梅Queen, 就把桃(1,3)比下去, 桃Queen
只好改以桃(2,1)為第一志願改找磚King, 又恰好是磚King的第一志願, 就成了.
黑Queen的(1,4)落選, 改以(2,3)為第一志願, 但又輸給桃(2,1),就再改(3,4)
為第一志願, 此時桃King只有此份表白, 就配對了.
最後的配對是(1,1), (2,1), (2,1), (3,4)
這個算法先從 Queen 開始表白, 但若先從 King 開始, 得到的 stable matching
也是相同的解.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.168.148.216
※ 文章網址: https://webptt.com/m.aspx?n=bbs/AfterPhD/M.1472227758.A.2F3.html
1F：→ YoursEver: stable marriage problem 08/27 00:47
2F：推 jabari: 人們無法找到完美伴侶 而是選擇能夠接受的 08/27 10:47
3F：推 expiate: 謝謝你的介紹 08/27 11:26
4F：推 adifdtd: Hall's Thm, systems of distinct representatives (SDR) 08/27 12:15