刘玉铭,
北京师范大学数学科学学院，100875，北京
基金项目:国家自然科学基金资助项目（11971065，11571001）； 数字福建智能制造大数据研究所开放课题资助项目（BD201810）
详细信息
通讯作者:刘玉铭（1968—），男，博士，高级工程师. 研究方向：模糊数学，图像处理，智能控制. E-mail：liuyuming@bnu.edu.cn
中图分类号:O29; TP301.6计量
文章访问数:231
HTML全文浏览量:128
PDF下载量:25
被引次数:0
出版历程
收稿日期:2019-09-10
网络出版日期:2021-01-21
刊出日期:2021-05-08
Extended Kuhn-Munkres algorithm for constrained matching search
Fangyang WANG,Yuming LIU,
School of Mathematical Sciences, Beijing Normal University, 100875, Beijing, China
摘要
HTML全文
图
参考文献
相关文章
施引文献
资源附件
访问统计
摘要
摘要:提出了扩展的Kuhn-Munkres算法，可解决带下界约束的局部匹配存在性问题，即在匹配全集的给定子集中，搜索得到一个二分图匹配满足其边权和大于给定阈值．扩展Kuhn-Munkres算法构造了一棵以Kuhn-Munkres算法中间过程为节点的搜索树，利用搜索优先级和剪枝，将算法时间复杂度降低至二分图匹配全集与给定子集差集规模的多项式函数．
关键词:二分图/
最优匹配/
Kuhn-Munkres算法
Abstract:With Kuhn-Munkres algorithm no optimal matching is founded on matching subset．An extended Kuhn-Munkres algorithm is proposed here to solve this problem of local matching with lower bound constraints, to search for a bipartite graph matching with edge-weights greater than a given threshold from a given matching subset．At present, there is no polynomial algorithm to solve this problem while the time complexity of general search algorithm is exponential．Extended Kuhn-Munkres algorithm constructs a search tree with an intermediate process of Kuhn-Munkres algorithm as nodes．With search priority and pruning, time complexity of searching for result matching is reduced to a polynomial function about the size of bipartite graph and the size of the difference set between the whole matching set and a given matching subset．
Key words:bipartite graph/
optimal matching/
Kuhn-Munkres algorithm
