作者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/cn.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