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

Extended Kuhn-Munkres algorithm for constrained matching search

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

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.