针对带约束匹配搜索的扩展Kuhn-Munkres算法

• 作者: 王方洋 刘玉铭
• 来源期刊: 北京师范大学学报（自然科学版）
• 关键词: 二分图 最优匹配 Kuhn-Munkres算法
• 年，卷（期）: 2021,（2）
• 页码范围: 167-172
• 页数: 6页
• 分类号: O29|TP301.6
• 语种: 中文
• DOI: 10.12202/j.0476-0301.2019242

摘要

提出了扩展的Kuhn-Munkres算法,可解决带下界约束的局部匹配存在性问题,即在匹配全集的给定子集中,搜索得到一个二分图匹配满足其边权和大于给定阈值.扩展Kuhn-Munkres算法构造了一棵以Kuhn-Munkres算法中间过程为节点的搜索树,利用搜索优先级和剪枝,将算法时间复杂度降低至二分图匹配全集与给定子集差集规模的多项式函数.