算法设计与分析课程设计报告稳定婚姻问题的GaleShapley算法江苏大学版本Word文档下载推荐.docx
- 文档编号:5147948
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:2
- 大小:21.41KB
算法设计与分析课程设计报告稳定婚姻问题的GaleShapley算法江苏大学版本Word文档下载推荐.docx
《算法设计与分析课程设计报告稳定婚姻问题的GaleShapley算法江苏大学版本Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《算法设计与分析课程设计报告稳定婚姻问题的GaleShapley算法江苏大学版本Word文档下载推荐.docx(2页珍藏版)》请在冰点文库上搜索。
模拟实现稳定婚姻问题的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.程序编制环境相关说明:
系统:
WINDOWS7
编制环境:
visualstudio8
二、程序主要算法设计分析说明
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)最后,当没有一个人是自由的时候,算法将结束;
此刻所有的约会将被宣告为最后的结果,且将返回最终的完美匹配。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 课程设计 报告 稳定 婚姻 问题 GaleShapley 江苏 大学 版本
链接地址:https://www.bingdoc.com/p-5147948.html