KM算法詳解及如何使用java實(shí)現(xiàn)

今天就跟大家聊聊有關(guān)KM算法詳解及如何使用java實(shí)現(xiàn)，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

匈牙利算法

基本概念

• 二分圖:二分圖又稱為二部圖.簡(jiǎn)單來說，如果圖中點(diǎn)可以被分為兩組，并且使得所有邊都跨越組的邊界，則這就是一個(gè)二分圖。準(zhǔn)確地說：把一個(gè)圖的頂點(diǎn)劃分為兩個(gè)不相交集 U 和V ，使得每一條邊都分別連接U、V中的頂點(diǎn)。如果存在這樣的劃分，則此圖為一個(gè)二分圖。二分圖的一個(gè)等價(jià)定義是：不含有"含奇數(shù)條邊的環(huán)"的圖。生成子圖:子圖包含原圖的所有頂點(diǎn)

• 匹配: 通俗的說:匹配（matching）是一個(gè)邊的集合，其中任意兩條邊都沒有公共頂點(diǎn).定義:對(duì)給定二分圖G,在G的子圖M中,M的邊集{E}中的任意兩條邊不依賴于同一個(gè)頂點(diǎn),則稱M為一個(gè)匹配

• 最大匹配: 圖的所有匹配中,含有邊數(shù)最多的匹配稱為最大匹配

• 完備匹配: 如果圖G的某個(gè)匹配M,使G的每個(gè)頂點(diǎn)都和匹配M中的某條邊相關(guān)聯(lián),則稱M為完全匹配(完備匹配); 完備匹配一定是最大匹配.

• ?

• 如圖: Fig.1為一個(gè)二分圖,將其改為Fig.2的形式更為直觀;Fig.3 紅線部分,為一個(gè)匹配; Fig.4 為一個(gè)最大匹配,也是一個(gè)完備匹配

求圖最大匹配的匈牙利算法

• 求最大匹配最直接暴力的方法是: 找出全部匹配,然后保留邊最多的. 這個(gè)方法的復(fù)雜度為邊數(shù)目的指數(shù)級(jí)函數(shù). 匈牙利算法是效率更高的方法.

• 增廣路徑: 若P是圖G一條連通兩個(gè)未匹配點(diǎn)的路徑,并且屬于匹配M的邊和不屬于M的邊(即已匹配邊和未匹配邊)在P上交替出現(xiàn),則稱P為相對(duì)于M的一條增廣路徑.

• ?

• 如上圖,Fig.5紅色為匹配,Fig.6為相對(duì)于匹配的一條增廣路徑

• 由增廣路徑的定義,可以推出三個(gè)結(jié)論:

1. P的路徑長(zhǎng)度必定為奇數(shù),第一條邊和最后一條邊都不屬于M;

2. P經(jīng)過取反操作,可以得到一個(gè)更大的匹配M1;

3. M為G的最大匹配當(dāng)且僅當(dāng)不存在相對(duì)于M的增廣路徑.

• 匈牙利算法: 用增廣路徑求最大匹配(匈牙利科學(xué)家Edmonds于1965年提出); 其框架如下:

1. 置M為空;

2. 找出一條增廣路徑P,通過取反操作,得到更大的匹配M1;

3. 重復(fù)步驟2,直到找不出增廣路徑為止.

• 匈牙利算法實(shí)現(xiàn)(java)

• ?

• 增廣路徑有兩種尋徑方法，一個(gè)是深搜(DFS)，一個(gè)是寬搜(BFS)。如上圖,藍(lán)色線為第一次匹配子圖,現(xiàn)在從x1尋找增廣路徑,如果是DFS深搜:首先:x1找到y(tǒng)0,發(fā)現(xiàn)y0已經(jīng)被x0匹配,于是深入到x0,為x0找新的匹配點(diǎn),發(fā)現(xiàn)x0可以匹配y2,讓x0與y2匹配,然后讓x1與y0匹配,得到第二次匹配子圖(紅色).現(xiàn)在,從x2出發(fā),搜尋增廣路徑,x2找到y(tǒng)0匹配，但發(fā)現(xiàn)y0已經(jīng)被x1匹配了，于是就深入到x1，去為x1找新的匹配節(jié)點(diǎn)，結(jié)果發(fā)現(xiàn)x1沒有其他的匹配節(jié)點(diǎn)，于是匹配失敗，x2接著找y1，發(fā)現(xiàn)y1可以匹配，于是就找到了新的增廣路徑,將x2-y1加入匹配中。

• DFS實(shí)現(xiàn)代碼見我的代碼java實(shí)現(xiàn)|GitHub

KM算法

KM算法原理

• 對(duì)于加權(quán)完全二分圖,找出權(quán)和最大的匹配,叫做求最佳匹配; 直接窮舉法:效率為n!;用KM算法.

• 定理: 設(shè)M是一個(gè)帶權(quá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,都有l(wèi)x[i]+ly[j]>=w[i,j]成立(w[i,j]表示邊的權(quán))，且對(duì)所有的邊(i,j) in M,都有l(wèi)x[i]+ly[j]=w[i,j]成立，則M是圖G的一個(gè)最佳匹配。證明很容易。

• 對(duì)任意的G和M,可行標(biāo)都是存在的

• 對(duì)二分圖G和一組可行標(biāo),滿足可行標(biāo)邊界條件(lx[i]+ly[j]=w[i,j])的所有邊構(gòu)成的生成子圖(需要包含所有頂點(diǎn)),稱為其等價(jià)子圖(相等子圖),在這個(gè)等價(jià)子圖上,尋找其完備匹配,如果完備匹配存在,則這個(gè)完備匹配M就是圖G的最大權(quán)匹配,最大權(quán)等于所有可行標(biāo)的和; 如果完備匹配不存在,則修改可行標(biāo),用貪心的思想,將最優(yōu)的邊加入等價(jià)子圖. KM算法就是一種逐次修改可行頂標(biāo)的方法,使之對(duì)應(yīng)的等價(jià)子圖逐次增廣(增加邊),最后出現(xiàn)完備匹配.

KM算法流程及實(shí)例

• Kuhn－Munkras算法流程：

1. 初始化可行頂標(biāo)的值

2. 用匈牙利算法在等價(jià)子圖中尋找完備匹配

3. 若未找到完備匹配則修改可行頂標(biāo)的值

4. 重復(fù)(2)(3)直到找到相等子圖的完備匹配為止

• 實(shí)例解釋算法過程:

• 帶權(quán)二分圖如下:

• ?

• ?

• 從x0找增廣路徑，找到x0-y4；然后,從x1找不到增廣路徑,這時(shí),需要修改頂標(biāo),加入一條最優(yōu)的新邊到等價(jià)子圖中:此時(shí)搜索過的路徑為x1-y4-x0(用匈牙利法DFS),在路徑上的X頂點(diǎn)集為S(x0,x1),Y頂點(diǎn)集為T(y4),對(duì)所有在S中的點(diǎn)xi及不在T中的點(diǎn)yj，計(jì)算d=min{(L(xi)+L(yj)-weight(xiyj))}，S中的點(diǎn)的頂標(biāo)減去d,T中的點(diǎn)的頂標(biāo)加上d,保持頂標(biāo)依然為可行頂標(biāo).(這個(gè)d計(jì)算的意義是貪心思想,兩種情況:此時(shí)讓x0與其他點(diǎn)匹配,x1與y4匹配;x0依舊與y4匹配,x1找其他點(diǎn)匹配.d計(jì)算的是找到一條新加的邊,讓x0和x1都搭配后,與x0和x1都同y4搭配的非法搭配這種情況相比,損失的權(quán)重值最少).具體來說:此時(shí)算出來的最小d=L(X1)+L(Y0)-weight(X1Y0)=2,對(duì)頂標(biāo)進(jìn)行松弛后,得到的等價(jià)子圖如上,加了一條邊x1-y0,為x1重新找增廣路徑,找到x1-y0,此時(shí)匹配權(quán)值和為9+6=15;原來的非法匹配權(quán)值和為9+8=17,"損失"的權(quán)值最少為2(即加入一條其他的非x1-y0的邊如x0-y2,損失的權(quán)值為3,比2大,即貪心思想,"損失最小").

• KM算法原本的時(shí)間復(fù)雜度為O(n^{4),n個(gè)節(jié)點(diǎn)找n次增廣路徑,在某次找增光路徑之中,頂標(biāo)最多改變n次,修改頂標(biāo)的松弛量需n2;} 可改進(jìn)為O(n^{3)時(shí)間復(fù)雜度:在尋找增廣路徑時(shí)順便將slack值算出.}

看完上述內(nèi)容，你們對(duì)KM算法詳解及如何使用java實(shí)現(xiàn)有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。