二分圖最佳匹配

二分圖最佳匹配，計算機術語，如果G為加權二分圖,則權值和最大的完備匹配稱為最佳匹配.

如果G為加權二分圖,則權值和最大的完備匹配稱為最佳匹配.
求一個二分圖的最佳匹配的普遍算法是KM(Kuhn-Munkres)算法.
KM算法的基本思想是,把權值轉化為可行頂標,再用匈牙利算法求出一組完備匹配,如果無法求出完備匹配,則修改可行頂標,直至找到完備匹配為止,這時的完備匹配為最佳匹配.
Kuhn－Munkras算法流程：
(1)初始化可行頂標的值
(2)用匈牙利算法尋找完備匹配
(3)若未找到完備匹配則修改可行頂標的值
(4)重複(2)(3)直到找到相等子圖的完備匹配為止