文献类型：期刊文章

作　　者：宋旭东[1] 纪秀花[1]

机构地区：[1]山东经济学院计算机科学与技术学院,山东济南250014

出　　处：《工程图学学报》

基　　金：国家自然科学基金资助项目(60573114);山东省自然科学基金资助项目(Y2005G15);山东省教育厅科技资助项目(J07YJ10)

年　　份：2010

卷　　号：31

期　　号：3

起止页码：187-192

语　　种：中文

收录情况：BDHX、BDHX2008、CSCD、CSCD_E2011_2012、JST、核心刊

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

关 键 词：计算机应用 算法理论  稳定婚姻匹配  先序遍历 森林  枚举  

分 类 号：TP391]