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

《算法设计与分析课程设计报告——稳定婚姻问题的gale-shapley算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、要算法设计分析说明Gale-Shapley算法的基本思想如下：(1)初始，每个人都是未婚的。假设一个未婚的男人m选择了他的优先表上排名最高的女人w，并且向她求婚。能立刻声明(m,w)将是最后的稳定匹配中的一对吗?不一定:因为在将来的某个时候，女人w偏爱的男人m，可能向她求婚。另一方面，对w来说，立刻拒绝m可能是危险的，她可能没有接收到来自她的优先表上排名像m那样高的某个人的求婚。于是一种自然地想法是使这个(m,w)对进入一种中间状态一约会。(2)假设我们现在处在某种状态，某些男人和女人是自由的(没有约会)，某些是有约会的。任意一个自由的男人m选择他还没有求过婚的最高排名的

3、女人w，且向她求婚。如果w也是自由的，那么m和w就成为约会状态。否则，w已经在与某个其他的男人m，约会。在这种情况下，她来决定m和m，哪个人在她的优先表中的排名更高;排名更高的男人变成与w约会而另一个人变成自由的。(3)最后，当没有一个人是自由的时候，算法将结束;此刻所有的约会将被宣告10/10为最后的结果，且将返回最终的完美匹配。所以，在N对男女中，男生采用主动出击追求自己最喜欢的女生策略，女生采用“守株待兔”和“喜新厌旧”策略。每一位男生主动去追求自己最喜欢的女生，而女生则在追求自己的男生中与现任男友中，选择一位最喜欢的接受。如果追求成功，为被抛弃的男友追求他下一位喜

4、欢的女生。如果追求不成功，则为这位男生追求他下一位喜欢的女生。这样进行了N次循环后，每一位男生都是从自己最喜欢的女生开始追求，并且都有女友，那么男生喜欢的程度多于现任妻子的那位女生肯定是曾经拒绝过自己的。同理，女生也是按照自己喜欢程度进行选择的。那么也不会出现不稳定问题。一、程序模块说明1.总体设计说明：程序采用两个二维数组man[max][max],woman[max][max]来记录max位男生，女生对异性的喜欢程度顺序。数组acman[]记录男生下一位追求的女生顺序（最开始从0位，也就是最喜欢的一位开始）；数组acwoman[]记录每一位女生当前男友（最开始设置一位

5、虚拟男友，其喜欢程度最小）采用4个for循环，分别对4个数组初始化。采用一个for循环遍历man数组（为每一位男生追求其最喜欢的女生）采用一个for循环输出结果2.模块说明：2.1模块一：boolchangeBF(vector>woman,inti,intnewBF,intoldBF,intmax)函数(1)概要说明：判断某位女生的当前男友与追求她的男友的排位顺序（喜欢程度）(2)关键数据结构和算法及其分析（比较newBF和oldBF在数组woman[][max]的序号大小，从而判断喜欢程度）(3)输入（数组woman[][]）10/10(1)输出

6、(bool类型1,0)一、总结（含主函数设计说明）稳定婚姻问题被应用到许多实际问题的处理过程中，例如学生的入学，工作招聘，医生和医院进行匹配等等.虽然稳定婚姻问题是一个NP问题，但是为找到所有的稳定匹配结果，我们设计了基于先序遍历森林的算法，利用此算法，对于众多不同的婚姻匹配，不会重复判断它们包含相同的配对子部分，这样大大节省了时间。为了进一步提高速度，由Gale-Shapley算法的性质得到一个定律及其推论，利用推论对算法做了进一步改进，减少了时间复杂度。课程设计是一项复杂的工作，在程序设计的过程中，许多我们认为应该是正确的代码，往往不能运行我们想要的结果。这就需要我们

7、的耐心与细心，去纠正任何一个可能的细小错误。此次算法课程设计，我将所学到的知识运用到了实践中，虽然在设计过程中遇到很大的困难，一开始的时候并不知道稳定婚姻问题的算法思想，但是在老师和同学的帮助下，我理解了Gale-Shapley算法的思想。在数据结构实现的过程中，我试过用结构体，链表等数据结构，最后还是觉得直接用数组最简洁。确定了用二维数组，程序就基本定下来了，主函数就是对二维数组的遍历。为了实现多样化，我在对二维数组初始化时采用了由用户输入实现初10/10始化。这里用到了动态数组的知识。在整个实验的过程中，遇到不少困难，但是