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

算法设计与分析课程设计题目:模拟实现稳定婚姻问题的Gale-Shapley算法 设计分析测试报告 姓名：张建彬 学号：3100608024 班级：软件1001指导教师：蒋丽萍 2013年1月 12日程序算法设计说明书一、 前言1.问题描述：稳定婚姻问题：有n男n女，每人都按他对（异性）对象的喜好程度按1至n排列。安排男女结婚，使得下列情形为真:在n男n女中的任意两对夫妇(M, W)和(m, w)，都不存在M男对w女喜好度大于现任妻子W女，并且w女对M男喜好度也大于现任丈夫m男的情形发生，此种情形称为不稳定。2.程序编制环境相关说明：系统：WINDOWS 7编制环境：visual studio 8二、 程序主要算法设计分析说明Gale-Shapley算法的基本思想如下： (1)初始，每个人都是未婚的。假设一个未婚的男人m选择了他的优先表上排名最高的女人w，并且向她求婚。能立刻声明(m, w)将是最后的稳定匹配中的一对吗?不一定:因为在将来的某个时候，女人w偏爱的男人m，可能向她求婚。另一方面，对w来说，立刻拒绝m可能是危险的，她可能没有接收到来自她的优先表上排名像m那样高的某个人的求婚。于是一种自然地想法是使这个(m, w)对进入一种中间状态一约会。 (2)假设我们现在处在某种状态，某些男人和女人是自由的(没有约会)，某些是有约会的。任意一个自由的男人m选择他还没有求过婚的最高排名的女人w，且向她求婚。如果w也是自由的，那么m和w就成为约会状态。否则，w已经在与某个其他的男人m，约会。在这种情况下，她来决定m和m，哪 个人在她的优先表中的排名更高;排名更高的男人变成与w约会而另一个人变成自由的。(3)最后，当没有一个人是自由的时候，算法将结束;此刻所有的约会将被宣告为最后的结果，且将返回最终的完美匹配。所以，在N对男女中，男生采用主动出击追求自己最喜欢的女生策略，女生采用“守株待兔”和“喜新厌旧”策略。每一位男生主动去追求自己最喜欢的女生，而女生则在追求自己的男生中与现任男友中，选择一位最喜欢的接受。如果追求成功，为被抛弃的男友追求他下一位喜欢的女生。如果追求不成功，则为这位男生追求他下一位喜欢的女生。这样进行了N次循环后，每一位男生都是从自己最喜欢的女生开始追求，并且都有女友，那么男生喜欢的程度多于现任妻子的那位女生肯定是曾经拒绝过自己的。同理，女生也是按照自己喜欢程度进行选择的。那么也不会出现不稳定问题。三、 程序模块说明1. 总体设计说明：程序采用两个二维数组manmaxmax,womanmaxmax来记录max位男生，女生对异性的喜欢程度顺序。数组acman记录男生下一位追求的女生顺序（最开始从0位，也就是最喜欢的一位开始）；数组acwoman记录每一位女生当前男友（最开始设置一位虚拟男友，其喜欢程度最小）采用4个for循环，分别对4个数组初始化。采用一个for循环遍历man数组（为每一位男生追求其最喜欢的女生）采用一个for循环输出结果2. 模块说明：2.1 模块一：bool changeBF(vectorvector woman,int i,int newBF,int oldBF,int max)函数(1) 概要说明：判断某位女生的当前男友与追求她的男友的排位顺序（喜欢程度）(2) 关键数据结构和算法及其分析（比较newBF和oldBF在数组womanmax的序号大小，从而判断喜欢程度）(3) 输入（数组woman）(4) 输出(bool类型1,0)四、 总结（含主函数设计说明）稳定婚姻问题被应用到许多实际问题的处理过程中，例如学生的入学，工作招聘，医生和医院进行匹配等等.虽然稳定婚姻问题是一个NP问题，但是为找到所有的稳定匹配结果，我们设计了基于先序遍历森林的算法，利用此算法，对于众多不同的婚姻匹配，不会重复判断它们包含相同的配对子部分，这样大大节省了时间。为了进一步提高速度，由Gale-Shapley算法的性质得到一个定律及其推论，利用推论对算法做了进一步改进，减少了时间复杂度。课程设计是一项复杂的工作，在程序设计的过程中，许多我们认为应该是正确的代码，往往不能运行我们想要的结果。这就需要我们的耐心与细心，去纠正任何一个可能的细小错误。此次算法课程设计，我将所学到的知识运用到了实践中，虽然在设计过程中遇到很大的困难，一开始的时候并不知道稳定婚姻问题的算法思想，但是在老师和同学的帮助下，我理解了Gale-Shapley算法的思想。在数据结构实现的过程中，我试过用结构体，链表等数据结构，最后还是觉得直接用数组最简洁。确定了用二维数组，程序就基本定下来了，主函数就是对二维数组的遍历。为了实现多样化，我在对二维数组初始化时采用了由用户输入实现初始化。这里用到了动态数组的知识。在整个实验的过程中，遇到不少困难，但是最终得以克服，并且最终获得了成功。经历这次课程设计，我深深体会到算法的神奇，我们要编写一段代码，首先要有一种算法思路，这是至关重要的，甚至可以成为编程的灵魂，但是算法思想比较难以想到，这就需要我们在以后的实践中经常锻炼，经常思考，培养自己思考能力，这样才能不断进步。五、参考文献清华大学出版社算法设计与分析程序及算法测试报告一、 前言1. 测试目的及采用的主要测试方法目的：测试该程序能否成功对N对男女成功配对，且婚姻稳定。测试方法：设置不同的数据，判断是否有错误。被测试程序算法说明及流程图等代码：#include#include using namespace std;void main()int newBF;int oldBF;int t;int search;int max;cout输入男生人数（女生）：max;int *nextm=new intmax+1; /男生下个追求女士的号码int *nextw=new intmax+1;/女士接受的男生号vectorvector man(max, vector(max);/男生对女士的喜欢程度顺序vectorvector woman(max, vector(max+1);/女生对男生的喜欢程度顺序for(int i=0;imax+1;i+)nextmi=0;for(int i=0;imax;i+)nextwi=max;/对数组初始化for(int i=0;imax;i+)cout第i位男士喜欢女生顺序为：endl;for(int j=0;jmanij;for(int i=0;imax;i+)cout第i位女士喜欢男生顺序为：endl;for(int j=0;jwomanij;womanimax=max;bool changeBF(vectorvector woman,int,int,int,int);for(int j=0;jj)/什么也不做elsej=oldBF;/前任男友被抛弃，且号码小，应让其重新最求女生j-;elsenextmj+;/最求不成功，继续追求下一位喜欢的女生j-;for(int j=0;jmax;j+)cout第j位男士的女友是manjnextmjendl;bool changeBF(vectorvector woman,int i,int newBF,int oldBF,int max)int temp1;int temp2;for(int j=0;j=max;j+)if(womanij=newBF)temp1=j;break;for(int j=0;j=max;j+)if(womanij=oldBF)temp2=j;break;return(temp1temp2);/比较前任与现任的排序先后2. 测试环境说明系统：WINDOWS 7测试环境：visual studio 8二、 测试用例说明1. 测试用例1目的：判断是否一对一的配对输入预期输出：不会出现重复数字实际输出测试结果：显示每一位男生都唯一配对以为女生2. 测试用例2目的：测试每一位配对的组合是否婚姻稳定输入预期输出：0 3 2