穩(wěn)定婚姻問題(Stable Marriage Problem) - 農(nóng)夫三拳 - 博客

穩(wěn)定婚姻問題(Stable Marriage Problem)


2008-09-12 20:14
by
農(nóng)夫三拳,
1685
visits,
收藏,
編輯

穩(wěn)定婚姻是組合數(shù)學(xué)里面的一個(gè)問題。

問題大概是這樣：有一個(gè)社團(tuán)里有n個(gè)女生和n個(gè)男生，每位女生按照她的偏愛程度將男生排序，同時(shí)每位男生也按照自己的偏愛程度將女生排序。然后將這n個(gè)女生和n個(gè)男生配成完備婚姻。

如果存在兩位女生A和B，兩位男生a和b，使得A和a結(jié)婚，B和b結(jié)婚，但是A更偏愛b而不是a，b更偏愛A而不是B，則這個(gè)婚姻就是不穩(wěn)定的，A和b可能背著別人相伴而走，因?yàn)樗麄z都認(rèn)為，與當(dāng)前配偶比起來他們更偏愛各自的新伴侶。

如果完備婚姻不是不穩(wěn)定的，則稱其是穩(wěn)定的。通過證明，可以得到每一個(gè)n女n男的社團(tuán)，都存在穩(wěn)定婚姻的結(jié)論。但是這種情況只在異性的社團(tuán)中存在。也就是說在同性的社團(tuán)里面，穩(wěn)定婚姻的存在性將不再被保證。

Gale-Shapley 算法

while? 存在男人m是自由的且還沒對每個(gè)女人都求過婚

????? 選擇這個(gè)男人m

??????????????? 令w是m的優(yōu)先表中還沒求過婚的最高排名的女人

??????? if? w是自由的

??????????? （m，w）變成約會(huì)狀態(tài)

??????? else? w當(dāng)前與m1約會(huì)

????????????? if? w更偏愛m1而不愛m

????????????????????????????????? m保持自由

????????????? else??? w更偏愛m而不愛m1

??????????????????????????????????????? （m，w）變成約會(huì)狀態(tài)

??????????????????? m1變成自由

????????????? endif

????????????????? endif

endwhile

下面是兩道關(guān)于 穩(wěn)定婚姻問題 的題目:

1. ZJU 1576 Marriage is Stable

2. NKU 1710 帥小伙子和漂亮姑娘

3. PKU 3487 The Stable Marriage Problem

穩(wěn)定婚姻問題(Stable Marriage Problem)