一种多层级二分图最大匹配问题的快速算法
Algorithm for Layered Bipartite Graph Maximum Matching Problem
主令恒 1顾丹鹏 1唐松强 1陈肖勇1
作者信息
- 1. 中国电建集团华东勘测设计研究院有限公司,浙江 杭州 310000;浙江华东工程数字技术有限公司,浙江 杭州 310000
- 折叠
摘要
本文提出一种新的二分匹配问题模型,该问题的特点是待匹配的对象包含子对象,即存在父子关系,在对子对象进行匹配的同时也需要对父对象进行匹配.该模型可应用于多种场景,典型的场景如数据库模式匹配、团队比赛匹配.本文针对该匹配问题,提出一个多项式时间的算法,该算法的整体思路是将问题分解为2个经典问题的组合:二分图最大匹配和最大权匹配.这2个经典问题都有成熟的算法可以解决,分别是匈牙利算法和KM算法.算法在组合的过程中采取了贪心策略,在子对象这一层应用最大匹配问题,之后将匹配数作为权值,在父对象这层应用最大权匹配问题,从而得到最终结果.本文给出了其正确性的证明,并对算法的性能进行了实验分析.
Abstract
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.
关键词
二分图/最大匹配/最大权匹配/模式匹配/贪心策略Key words
layered bipartite graph/maximum matching/weighted maximum matching/pattern matching/greedy strategy引用本文复制引用
基金项目
国家重点研发计划项目(2022YFB2602101)
出版年
2024
国家科技期刊平台
NSTL
万方数据