關(guān)于匈奴利算法，什么是匈牙利算法這個(gè)很多人還不知道，今天菲菲來為大家解答以上的問題，現(xiàn)在讓我們一起來看看吧！

1、談匈牙利算法自然避不開Hall定理，即是：對(duì)于二部圖G，存在一個(gè)匹配M，使得X的所有頂點(diǎn)關(guān)于M飽和的充要條件是：對(duì)于X的任意一個(gè)子集A，和A鄰接的點(diǎn)集為T(A)，恒有： │T(A)│ >= │A│ 匈牙利算法是基于Hall定理中充分性證明的思想，其基本步驟為： 1．任給初始匹配M； 2．若X已飽和則結(jié)束，否則進(jìn)行第3步； 3．在X中找到一個(gè)非飽和頂點(diǎn)x0，作V1 ← {x0}, V2 ← Φ； 4．若T(V1) = V2則因?yàn)闊o法匹配而停止，否則任選一點(diǎn)y ∈T(V1)V2； 5．若y已飽和則轉(zhuǎn)6，否則做一條從x0 →y的可增廣道路P，M←M?E(P)，轉(zhuǎn)2； 6．由于y已飽和，所以M中有一條邊(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 轉(zhuǎn)4； 設(shè)數(shù)組up[1..n] --- 標(biāo)記二分圖的上半部分的點(diǎn)。

2、 down[1..n] --- 標(biāo)記二分圖的下半部分的點(diǎn)。

3、 map[1..n，1..n] --- 表示二分圖的上，下部分的點(diǎn)的關(guān)系。

4、 True-相連， false---不相連。

5、 over1[1..n]，over2[1..n] 標(biāo)記上下部分的已蓋點(diǎn)。

6、 use[1..n，1..n] - 表示該條邊是否被覆蓋 。

7、 首先對(duì)讀入數(shù)據(jù)進(jìn)行處理 ，對(duì)于一條邊(x，y) ，起點(diǎn)進(jìn)集合up，終點(diǎn)進(jìn)集合down。

8、 標(biāo)記map中對(duì)應(yīng)元素為true。

9、 1. 尋找up中一個(gè)未蓋點(diǎn) 。

10、 2. 從該未蓋點(diǎn)出發(fā) ，搜索一條可行的路線 ，即由細(xì)邊出發(fā)， 由細(xì)邊結(jié)束， 且細(xì)粗交錯(cuò)的路線 。

11、 3. 若找到 ，則修改該路線上的點(diǎn)所對(duì)應(yīng)的over1，over2，use的元素。

12、重復(fù)步驟1。

13、 4. 統(tǒng)計(jì)use中已覆蓋的邊的條數(shù)total，總數(shù)n減去total即為問題的解。

本文到此分享完畢，希望對(duì)大家有所幫助。

　　免責(zé)聲明：本文由用戶上傳，與本網(wǎng)站立場(chǎng)無關(guān)。財(cái)經(jīng)信息僅供讀者參考，并不構(gòu)成投資建議。投資者據(jù)此操作，風(fēng)險(xiǎn)自擔(dān)。 如有侵權(quán)請(qǐng)聯(lián)系刪除！