我还是一个大一新生的时候,我们上了Pascal编程语言的第一课。那节课讲的的是“稳定婚姻”问题。
我们老师的教学方法不愧为一股清流,总能把各种术语变成m**chos、b**ches等粗话,让我们很是吃鲸。不得不说,这种方法还真挺有用的,直到现在我都记得那节课的内容。
一群男女正在寻找伴侣。每个人都有自己的钟意的对象,而我们要做的是根据这些偏好找到一个稳定的搭配方式。当一组配对的双方都无法找到一个双方相互喜欢的新配对时,我们可以称这个配对是稳定的。有没有觉得这个问题有点像求解纳什均衡?确实很像。
目前偏好规则如下:
- Adam喜欢Alice
- Bob喜欢Alice
- Alice喜欢Bob
- Betty喜欢Adam
不稳定组合:Adam-Alice,Bob-Betty
稳定组合:Adam-Betty,Bob-Alice
这个算法还是挺简单的。把每个男人按照他的喜好和一个女人配对。如果那个女人已经配对了,但是获得了另一个男性的青睐,那么她会离开原来的配对去另寻新欢。问题的难点在于证明这个解法的正确性。
算法实现
测试
(原作者:Tomáš Bouda)