C++ 匈牙利算法案例分析詳解
匈牙利算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性證明的思想,它是部圖匹配最常見的算法,該算法的核心就是尋找增廣路徑,它是一種用增廣路徑求二分圖最大匹配的算法。
-------等等,看得頭大?那么請(qǐng)看下面的版本:
通過數(shù)代人的努力,你終于趕上了剩男剩女的大潮,假設(shè)你是一位光榮的新世紀(jì)媒人,在你的手上有N個(gè)剩男,M個(gè)剩女,每個(gè)人都可能對(duì)多名異性有好感(-_-||暫時(shí)不考慮特殊的性取向),如果一對(duì)男女互有好感,那么你就可以把這一對(duì)撮合在一起,現(xiàn)在讓我們無視掉所有的單相思(好憂傷的感覺),你擁有的大概就是下面這樣一張關(guān)系圖,每一條連線都表示互有好感。
本著救人一命,勝造七級(jí)浮屠的原則,你想要盡可能地撮合更多的情侶,匈牙利算法的工作模式會(huì)教你這樣做:
一: 先試著給1號(hào)男生找妹子,發(fā)現(xiàn)第一個(gè)和他相連的1號(hào)女生還名花無主,got it,連上一條藍(lán)線
二:接著給2號(hào)男生找妹子,發(fā)現(xiàn)第一個(gè)和他相連的2號(hào)女生名花無主,got it
三:接下來是3號(hào)男生,很遺憾1號(hào)女生已經(jīng)有主了,怎么辦呢?
我們?cè)囍o之前1號(hào)女生匹配的男生(也就是1號(hào)男生)另外分配一個(gè)妹子。
(黃色表示這條邊被臨時(shí)拆掉)
與1號(hào)男生相連的第二個(gè)女生是2號(hào)女生,但是2號(hào)女生也有主了,怎么辦呢?我們?cè)僭囍o2號(hào)女生的原配重新找個(gè)妹子(注意這個(gè)步驟和上面是一樣的,這是一個(gè)遞歸的過程)
此時(shí)發(fā)現(xiàn)2號(hào)男生還能找到3號(hào)女生,那么之前的問題迎刃而解了,回溯回去
2號(hào)男生可以找3號(hào)妹子~~~ 1號(hào)男生可以找2號(hào)妹子了~~~ 3號(hào)男生可以找1號(hào)妹子
所以第三步最后的結(jié)果就是:
四: 接下來是4號(hào)男生,很遺憾,按照第三步的節(jié)奏我們沒法給4號(hào)男生騰出來一個(gè)妹子,我們實(shí)在是無能為力了……香吉士同學(xué)走好。
這就是匈牙利算法的流程,其中找妹子是個(gè)遞歸的過程,最最關(guān)鍵的字就是“ 騰”字
其原則大概是:有機(jī)會(huì)上,沒機(jī)會(huì)創(chuàng)造機(jī)會(huì)也要上
bool find(int x){ int i,j; for (j=1;j<=m;j++){ //掃描每個(gè)妹子 if (line[x][j]==true && used[j]==false) //如果有曖昧并且還沒有標(biāo)記過(這里標(biāo)記的意思是這次查找曾試圖改變過該妹子的歸屬問題,但是沒有成功,所以就不用瞎費(fèi)工夫了) { used[j]=1; if (girl[j]==0 || find(girl[j])) { //名花無主或者能騰出個(gè)位置來,這里使用遞歸 girl[j]=x; return true; } } } return false; }
在主程序我們這樣做:每一步相當(dāng)于我們上面描述的一二三四中的一步
for (i=1;i<=n;i++) { memset(used,0,sizeof(used)); //這個(gè)在每一步中清空 if find(i) all+=1; }
到此這篇關(guān)于C++ 匈牙利算法案例分析詳解的文章就介紹到這了,更多相關(guān)C++ 匈牙利算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)教職工信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)教職工信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn)
本文主要介紹了QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06C語言控制臺(tái)實(shí)現(xiàn)打飛機(jī)小游戲
這篇文章主要為大家詳細(xì)介紹了C語言控制臺(tái)實(shí)現(xiàn)打飛機(jī)小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-04-04C++學(xué)習(xí)進(jìn)階篇之類大小計(jì)算和this指針
this是C++中的一個(gè)關(guān)鍵字,也是一個(gè)const指針,它指向當(dāng)前對(duì)象,通過它可以訪問當(dāng)前對(duì)象的所有成員,下面這篇文章主要給大家介紹了關(guān)于C++學(xué)習(xí)進(jìn)階篇之類大小計(jì)算和this指針的相關(guān)資料,需要的朋友可以參考下2023-04-04