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