摘要
稳定匹配问题是算法理论中的典型问题之一,稳定婚姻匹配问题则是一种解决二部图匹配问题的模型。论文对稳定婚姻匹配问题进行了简单的阐述,并介绍了求解典型稳定婚姻问题的Gale-Shapley算法的基本思想及其性质。为了快速求出所有的稳定匹配结果,提出了基于先序遍历森林的快速枚举算法。由Gale-Shapley算法的性质得到一个定理及其推论,利用得到的推论对算法做了进一步改进和优化。在满足推论的特定条件下,提高了算法的执行效率。
The stable matching problem is one of the typical problems in the algorithm theory.The stable marriage matching problem is a model which can be used to solve the problem about bipartite graph matching.In this paper the stable marriage matching problem is introduced briefly,and the basic idea and property of the Gale-Shapley algorithm are described.And then a quick enumeration algorithm based on preorder traversal of forest is designed for quickly enumerating all the stable matching results.A theorem and its inference are derived from the property of the Gale-Shapley algorithm.The algorithm is further improved and optimized by utilizing the inference.The execution time of the original algorithm is improved in specified conditions where the inference is satisfied.
出处
《工程图学学报》
CSCD
北大核心
2010年第3期187-192,共6页
Journal of Engineering Graphics
基金
国家自然科学基金资助项目(60573114)
山东省自然科学基金资助项目(Y2005G15)
山东省教育厅科技资助项目(J07YJ10)
关键词
计算机应用
算法理论
稳定婚姻匹配
先序遍历
森林
枚举
computer application
algorithm theory
stable marriage matching
preorder traversal
forest
enumeration
