算法设计与分析课程设计报告——稳定婚姻问题的Gale-Shapley算法

1、 1/ 10 算法设计与分析课程设计算法设计与分析课程设计 题目题目:模拟实现稳定婚姻问题的模拟实现稳定婚姻问题的 Gale-Shapley 算法算法 设计分析测试报告设计分析测试报告 2013 年 1 月 12 日 2/ 10 程序算法设计说明书程序算法设计说明书 一、一、 前言前言 1.问题描述：稳定婚姻问题：有n男n女，每人都按他对（异性）对 象的喜好程度按1至n排列。安排男女结婚，使得下列情形为真:在n 男n女中的任意两对夫妇(M, W)和(m, w)，都不存在M男对w女喜好度 大于现任妻子W女， 并且w女对M男喜好度也大于现任丈夫m男的情形发 生，此种情形称为不稳定。 2.程序编制环

2、境相关说明： 系统：WINDOWS 7 编制环境：visual studio 8 二、二、 程序主要算法设计分析说明程序主要算法设计分析说明 Gale-Shapley 算法的基本思想如下： (1)初始，每个人都是未婚的。假设一个未婚的男人 m 选择了他的优先表上排 名最高的女人 w， 并且向她求婚。 能立刻声明(m, w)将是最后的稳定匹配中的 一对吗?不一定:因为在将来的某个时候，女人 w 偏爱的男人 m，可能向她求 婚。另一方面，对 w 来说，立刻拒绝 m 可能是危险的，她可能没有接收到来 自她的优先表上排名像 m 那样高的某个人的求婚。于是一种自然地想法是使 这个(m, w)对进入一种中

3、间状态一约会。 (2)假设我们现在处在某种状态，某些男人和女人是自由的(没有约会)，某些 是有约会的。任意一个自由的男人 m 选择他还没有求过婚的最高排名的女人 w，且向她求婚。如果 w 也是自由的，那么 m 和 w 就成为约会状态。否则， w 已经在与某个其他的男人 m，约会。在这种情况下，她来决定 m 和 m，哪 个人在她的优先表中的排名更高;排名更高的男人变成与 w 约会而另一个人 变成自由的。 (3)最后，当没有一个人是自由的时候，算法将结束;此刻所有的约会将被宣告 3/ 10 为最后的结果，且将返回最终的完美匹配。 所以，在 N 对男女中，男生采用主动出击追求自己最喜欢的女生策略，

4、女生采用“守株待兔”和“喜新厌旧”策略。每一位男生主动去追求自己最 喜欢的女生，而女生则在追求自己的男生中与现任男友中，选择一位最喜欢 的接受。如果追求成功，为被抛弃的男友追求他下一位喜欢的女生。如果追 求不成功， 则为这位男生追求他下一位喜欢的女生。 这样进行了 N 次循环后， 每一位男生都是从自己最喜欢的女生开始追求，并且都有女友，那么男生喜 欢的程度多于现任妻子的那位女生肯定是曾经拒绝过自己的。同理，女生也 是按照自己喜欢程度进行选择的。那么也不会出现不稳定问题。 三、三、 程序模块说明程序模块说明 1. 总体设计说明： 程序采用两个二维数组 manmaxmax,womanmaxmax来记录 max 位 男生，女生对异性的喜欢程度顺序。 数组 acman记录男生下一位追求的女生顺序（最开始从 0 位，也就是最 喜欢的一位开始） ； 数组 acwoman记录每一位女生当前男友 （最开始设置一位虚拟男友， 其 喜欢程度最小） 采用 4 个 for 循环，分别对 4 个数组初始化。 采用一个 for 循环遍历 man 数组（为每一位男生追求其最喜欢的女生） 采