二分圖匹配-匈牙利算法和km算法簡介(編輯修改稿)
2025-03-08 14:43 本頁面
【文章內(nèi)容簡介】 G的一個(gè)完備匹配，給每個(gè)頂點(diǎn)一個(gè)可行頂標(biāo) (第 i個(gè) x頂點(diǎn)的可行標(biāo)用 lx[i]表示，第 j個(gè) y頂點(diǎn)的可行標(biāo)用 ly[j]表示 )，如果對所有的邊 (i,j) in G,都有 lx[i]+ly[j]=w[i,j]成立 (w[i,j]表示邊的權(quán) )，且對所有的邊 (i,j) in M,都有 lx[i]+ly[j]=w[i,j]成立，則 M是圖 G的一個(gè)最佳匹配。證明很容易。KM算法v 對于任意的 G和 M，可行頂標(biāo)都是存在的：v l(x) = maxw(x,y)v l(y) = 0v 欲求完全二分圖的最佳匹配，只要用匈牙利算法求其相等子圖的完備匹配；問題是當(dāng)標(biāo)號之后的 Gl無完備匹配時(shí)怎么辦？ 1957年（居然比匈牙利算法早？？？）， Kuhn和 Munkras給出了一個(gè)解決該問題的有效算法，用逐次修改可行頂標(biāo) l(v)的辦法使對應(yīng)的相等子圖之最大匹配逐次增廣，最后出現(xiàn)完備匹配。KM算法v 修改方法如下：v 先將一個(gè)未被匹配的頂點(diǎn) u(u in {x})做一次增廣路，記下哪些結(jié)點(diǎn)被訪問那些結(jié)點(diǎn)沒有被訪問。求出d=min{lx[i]+ly[j]w[i,j]}其中 i結(jié)點(diǎn)被訪問， j結(jié)點(diǎn)沒有被訪問。然后調(diào)整 lx和 ly：對于訪問過的 x頂點(diǎn)，將它的可行標(biāo)減去 d，對于所有訪問過的 y頂點(diǎn)，將它的可行標(biāo)增加 d。修改后的頂標(biāo)仍是可行頂標(biāo)，原來的匹配 M仍然存在，相等子圖中至少出現(xiàn)了一條不屬于 M的邊，所以造成 M的逐漸增廣。KM算法v上述算法的證明也很容易vKuhn－ Munkras算法流程：v(1)初始化可行頂標(biāo)的值v(2)用匈牙利算法尋找完備匹配v(3)若未找到完備匹配則修改可行頂標(biāo)的值v(4)重復(fù) (2)(3)直到找到相等子圖的完備匹配為止參考文獻(xiàn)v王樹禾《離散數(shù)學(xué)引論》v吳文虎 王建德《圖論算法與程序設(shè)計(jì)》v劉汝佳 黃亮《算法藝術(shù)與信息學(xué)競賽》v2023年冬令營論文－孫方成 《 偶圖的算法及應(yīng)用》v2023年冬令營論文－黃源河《淺談圖論模型的建立與應(yīng)用》例題 1 Place the Robots（ ZOJ1654）問題描述 有一個(gè) N*M(N,M=50)的棋盤，棋盤的每一格是三種類型之一：空地
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1