工程图学学报
工程圖學學報
공정도학학보
JOURNAL OF ENGINEERING GRAPHICS
2010年
3期
187-192
,共6页
计算机应用%算法理论%稳定婚姻匹配%先序遍历%森林%枚举
計算機應用%算法理論%穩定婚姻匹配%先序遍歷%森林%枚舉
계산궤응용%산법이론%은정혼인필배%선서편력%삼림%매거
稳定匹配问题是算法理论中的典型问题之一,稳定婚姻匹配问题则是一种解决二部图匹配问题的模型.论文对稳定婚姻匹配问题进行了简单的阐述,并介绍了求解典型稳定婚姻问题的Gale-Shapley算法的基本思想及其性质.为了快速求出所有的稳定匹配结果,提出了基于先序遍历森林的快速枚举算法.由Gale-Shapley算法的性质得到一个定理及其推论,利用得到的推论对算法做了进一步改进和优化.在满足推论的特定条件下,提高了算法的执行效率.
穩定匹配問題是算法理論中的典型問題之一,穩定婚姻匹配問題則是一種解決二部圖匹配問題的模型.論文對穩定婚姻匹配問題進行瞭簡單的闡述,併介紹瞭求解典型穩定婚姻問題的Gale-Shapley算法的基本思想及其性質.為瞭快速求齣所有的穩定匹配結果,提齣瞭基于先序遍歷森林的快速枚舉算法.由Gale-Shapley算法的性質得到一箇定理及其推論,利用得到的推論對算法做瞭進一步改進和優化.在滿足推論的特定條件下,提高瞭算法的執行效率.
은정필배문제시산법이론중적전형문제지일,은정혼인필배문제칙시일충해결이부도필배문제적모형.논문대은정혼인필배문제진행료간단적천술,병개소료구해전형은정혼인문제적Gale-Shapley산법적기본사상급기성질.위료쾌속구출소유적은정필배결과,제출료기우선서편력삼림적쾌속매거산법.유Gale-Shapley산법적성질득도일개정리급기추론,이용득도적추론대산법주료진일보개진화우화.재만족추론적특정조건하,제고료산법적집행효솔.
