词条 | 二分图最佳匹配 |
释义 | 如果G为加权二分图,则权值和最大的完备匹配称为最佳匹配. 求一个二分图的最佳匹配的普遍算法是KM(Kuhn-Munkres)算法. KM算法的基本思想是,把权值转化为可行顶标,再用匈牙利算法求出一组完备匹配,如果无法求出完备匹配,则修改可行顶标,直至找到完备匹配为止,这时的完备匹配为最佳匹配. Kuhn-Munkras算法流程: (1)初始化可行顶标的值 (2)用匈牙利算法寻找完备匹配 (3)若未找到完备匹配则修改可行顶标的值 (4)重复(2)(3)直到找到相等子图的完备匹配为止 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。