二分圖匹配匈牙利算法和km算法簡介-wenkub
2023-03-09 14:29:42 本頁面
【正文】 ?用增廣路求最大匹配 (稱作匈牙利算法，匈牙利數(shù)學(xué)家 Edmonds于 1965年提出 ) ?算法輪廓： ? (1)置 M為空 ? (2)找出一條增廣路徑 P，通過取反操作獲得更大的匹配 M’代替 M ? (3)重復(fù) (2)操作直到找不出增廣路徑為止 匈牙利算法 ?程序清單： ? Function find(k:integer):integer。 ?增廣路的定義 (也稱增廣軌或交錯軌 )： ?若 P是圖 G中一條連通兩個未匹配頂點的路徑，并且屬 M的邊和不屬 M的邊 (即已匹配和待匹配的邊 )在 P上交替出現(xiàn)，則稱 P為相對于 M的一條增廣路徑。 ?選擇這樣的邊數(shù)最大的子集稱為圖的 最大匹配問題 (maximal matching problem) ?如果一個匹配中，圖中的每個頂點都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為 完全匹配 ，也稱作 完備匹配。 ?設(shè) G=(V,{R})是一個無向圖。如頂點集 V可分割為兩個互不相交的子集，并且圖中每條邊依附的兩個頂點都分屬兩個不同的子集。 匈牙利算法 ?求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。 匈牙利算法 ?由增廣路的定義可以推出下述三個結(jié)論： ? 1－ P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于 M。 ? var st,sf,i,j,t:integer。 sf := 1。 ? father[i] := queue[st]。 ? match2[i] := j。 匈牙利算法 ? end。 ? end。 ? end。 ? Writeln(Bmatch)。 KM算法 ?窮舉的效率－ n！，我們需要更加優(yōu)秀的算法。 KM算法 ?修改方法如下： ?先將一個未被匹配的頂點 u(u in {x})做一次增廣路，記下哪些結(jié)點被訪問那些結(jié)點沒有被訪問。 KM算法 ?上述算法的證明也很容易 ? Kuhn－ Munkras算法流程： ? (1)初始化可行頂標(biāo)的值 ? (2)用匈牙利算法尋找完備匹配 ? (3)若未找到完備匹配則修改可行頂標(biāo)的值 ? (4)重復(fù) (2)(3)直到找到相等子圖的完備匹配為止 參考文獻 ?王樹禾《離散數(shù)學(xué)引論》 ?吳文
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1