稳定婚姻匹配问题的一个快速枚举算法

• 作者: 宋旭东 纪秀花
• 来源期刊: 工程图学学报
• 学科: 工学
• 关键词: 计算机应用 算法理论 稳定婚姻匹配 先序遍历 森林 枚举
• 年，卷（期）: 2010,（3）
• 页码范围: 187-192
• 分类号: TP391
• 字数: 5256字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0158.2010.03.033

摘要

稳定匹配问题是算法理论中的典型问题之一,稳定婚姻匹配问题则是一种解决二部图匹配问题的模型.论文对稳定婚姻匹配问题进行了简单的阐述,并介绍了求解典型稳定婚姻问题的Gale-Shapley算法的基本思想及其性质.为了快速求出所有的稳定匹配结果,提出了基于先序遍历森林的快速枚举算法.由Gale-Shapley算法的性质得到一个定理及其推论,利用得到的推论对算法做了进一步改进和优化.在满足推论的特定条件下,提高了算法的执行效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	纪秀花	山东经济学院计算机科学与技术学院	9	82	6.0	9.0
2	宋旭东	山东经济学院计算机科学与技术学院	1	11	1.0	1.0