一种多层级二分图最大匹配问题的快速算法

作     者：主令恒 顾丹鹏 唐松强 陈肖勇 ZHU Lingheng;GU Danpeng;TANG Songqiang;CHEN Xiaoyong

作者机构：中国电建集团华东勘测设计研究院有限公司浙江杭州310000 浙江华东工程数字技术有限公司浙江杭州310000 

出 版 物：《计算机与现代化》 (Computer and Modernization)

年 卷 期：2024年第6期

页      面：59-63,102页

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家重点研发计划项目(2022YFB2602101) 

主　　题：二分图 最大匹配 最大权匹配 模式匹配 贪心策略 

摘      要：本文提出一种新的二分匹配问题模型,该问题的特点是待匹配的对象包含子对象,即存在父子关系,在对子对象进行匹配的同时也需要对父对象进行匹配。该模型可应用于多种场景,典型的场景如数据库模式匹配、团队比赛匹配。本文针对该匹配问题,提出一个多项式时间的算法,该算法的整体思路是将问题分解为2个经典问题的组合:二分图最大匹配和最大权匹配。这2个经典问题都有成熟的算法可以解决,分别是匈牙利算法和KM算法。算法在组合的过程中采取了贪心策略,在子对象这一层应用最大匹配问题,之后将匹配数作为权值,在父对象这层应用最大权匹配问题,从而得到最终结果。本文给出了其正确性的证明,并对算法的性能进行了实验分析。