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

Algorithm for Layered Bipartite Graph Maximum Matching Problem

作　　者：主令恒 顾丹鹏 唐松强 陈肖勇 ZHU Lingheng;GU Danpeng;TANG Songqiang;CHEN Xiaoyong(PowerChina Huadong Engineering Corporation Limited,Hangzhou,310000 China;Zhejiang Huadong Engineering Digital Technology Co.Ltd,Hangzhou,310000 China)

机构地区：[1]中国电建集团华东勘测设计研究院有限公司,浙江杭州310000 [2]浙江华东工程数字技术有限公司,浙江杭州310000

出　　处：《计算机与现代化》2024年第6期59-63,102,共6页Computer and Modernization

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

摘　　要：本文提出一种新的二分匹配问题模型,该问题的特点是待匹配的对象包含子对象,即存在父子关系,在对子对象进行匹配的同时也需要对父对象进行匹配。该模型可应用于多种场景,典型的场景如数据库模式匹配、团队比赛匹配。本文针对该匹配问题,提出一个多项式时间的算法,该算法的整体思路是将问题分解为2个经典问题的组合:二分图最大匹配和最大权匹配。这2个经典问题都有成熟的算法可以解决,分别是匈牙利算法和KM算法。算法在组合的过程中采取了贪心策略,在子对象这一层应用最大匹配问题,之后将匹配数作为权值,在父对象这层应用最大权匹配问题,从而得到最终结果。本文给出了其正确性的证明,并对算法的性能进行了实验分析。This paper brought up a new problem model for bipartite match problem.In this problem,the entities to be matched contains sub-entities which are also to be matched.That is,the entities to be matched has father-son relations.This model can be applied to many situation,like database schema match,and team match.This paper gave a polynomial-time algorithm,the idea of which is to break down this problem into a combination of Bipartite Graph Maximum Matching Problem and Weighted Maximum Matching Problem.There are mature algorithms(Hungarian Algorithm and Kuhn-Munkres Algorithm)that can solve these two classic problems.The process of the combination takes a kind of greedy strategy.Among sub-entities,Hungarian Algo‐rithm is applied.After that,we take the matching results as the weights and apply Kuhn-Munkres Algorithm among super entities,and then we get the final result.This paper also proved the correctness of this algorithm,and analyzed its performance through experiments.

关 键 词：二分图 最大匹配 最大权匹配 模式匹配 贪心策略 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]