| 针对带约束匹配搜索的扩展Kuhn-Munkres算法 |
| |
| 引用本文： | 王方洋,刘玉铭.针对带约束匹配搜索的扩展Kuhn-Munkres算法[J].北京师范大学学报(自然科学版),2021,57(2):167-172. |
| |
| 作者姓名： | 王方洋 刘玉铭 |
| |
| 作者单位： | 北京师范大学数学科学学院，100875，北京 |
| |
| 基金项目： | 国家自然科学基金资助项目（11971065，11571001）； 数字福建智能制造大数据研究所开放课题资助项目（BD201810） |
| |
| 摘 要： | 提出了扩展的Kuhn-Munkres算法，可解决带下界约束的局部匹配存在性问题，即在匹配全集的给定子集中，搜索得到一个二分图匹配满足其边权和大于给定阈值．扩展Kuhn-Munkres算法构造了一棵以Kuhn-Munkres算法中间过程为节点的搜索树，利用搜索优先级和剪枝，将算法时间复杂度降低至二分图匹配全集与给定子集差集规模的多项式函数．
|
| 关 键 词： | 二分图 最优匹配 Kuhn-Munkres算法 |
| 收稿时间： | 2019-09-10 |
Extended Kuhn-Munkres algorithm for constrained matching search |
| |
| WANG Fangyang,LIU Yuming.Extended Kuhn-Munkres algorithm for constrained matching search[J].Journal of Beijing Normal University(Natural Science),2021,57(2):167-172. |
| |
| Authors: | WANG Fangyang LIU Yuming |
| |
| Institution: | School of Mathematical Sciences, Beijing Normal University, 100875, Beijing, China |
| |
| 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． |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《北京师范大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《北京师范大学学报(自然科学版)》下载免费的PDF全文 |
