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

Abstract: 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.

Key words: computer application, algorithm theory, stable marriage matching, preorder traversal, forest, enumeration