二分圖(匈牙利,km算法詳解)(完整版)
【正文】 最優(yōu)匹配 KM算法 ? 算法流程 設(shè)頂點 Xi的頂標為 a[i]，頂點 Yi的頂標為 b[i] ? ⅰ .初始時， a[i]為與 Xi相關(guān)聯(lián)的邊的最大權(quán)值，b[j]=0，保證 a[i]+b[j]=w(i,j)成立 ? ⅱ .當相等子圖中不包含完備匹配時，就適當修改頂標以擴大相等子圖，直到找到完備匹配為止 ? ⅲ .修改頂標的方法 KM算法 ? 當從 Xi尋找增廣路失敗后，得到一棵交錯樹，它的所有葉子節(jié)點都是 X節(jié)點，對交錯樹中 X頂點的頂標減少 d值， Y頂點的頂標增加 d值，對于圖中所有的邊 (i,j)，可以看到 ? i和 j都不在交錯樹中，邊 (i,j)仍然不屬于相等子圖 ? i和 j都在交錯樹中，邊 (i,j)仍然屬于相等子圖 ? i不在交錯樹中， j在交錯樹中， a[i]+b[j]擴大，邊(i,j)不屬于相等子圖 KM算法 ? i在交錯樹 ,j不在交錯樹中 ,邊 (i,j)有可能加入到相等子圖中 ? 為了使 a[i]+b[j]=w(i,j)始終成立 ,且至少有一條邊加入到相等子圖中 ,d=min{a[i]+b[j]w(i,j)},i在交錯樹中 ,j不在交錯樹中 假設(shè)有 3個人 ,我們弄個簡化版的 .每個人與家的距離如下圖 第一個人到家 1,2,3的距離為 3,5,4,第二個人只能到家 1,2距離為 2,4,第三個人只能到家 3,距離為 7。 二分圖最優(yōu)匹配 ? 又稱帶權(quán)最大匹配。把所有頂點 i拆成兩個：Ｘ結(jié)點集中的 i和 Y結(jié)點集中的 i39。繼續(xù)轉(zhuǎn)到節(jié)點 1,發(fā)現(xiàn)節(jié)點 1的邊 14中節(jié)點 4還沒匹配 .于是我們找到了一個增廣路徑 增廣路如圖中箭頭所示 1 2 3 4 5 6 把圖中紅色線去掉 藍色線加上 1 2 3 4 5 6 1 2 3 4 5 6 找到一個更好的匹配 更改各自的匹配點 總結(jié) ? 所以流程就是 : ? 1,對于一個未匹配的節(jié)點 u,尋找它的每條邊 ,如果它的邊上的另一個節(jié)點 v還沒匹配則表明找到了一個匹配 ,直接轉(zhuǎn)步驟 4。 如右圖所示：藍色部分 就構(gòu)成一個最大匹配， 同時它也是一個完美匹 配 完美匹配： 如果所有點都在匹配邊上，稱這個最大 匹配是完美匹配。 二分圖的最大匹配 ? 定義：
電大資料相關(guān)推薦
鄂ICP備17016276號-1