C++ 匈牙利算法案例分析詳解
匈牙利算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性證明的思想,它是部圖匹配最常見(jiàn)的算法,該算法的核心就是尋找增廣路徑,它是一種用增廣路徑求二分圖最大匹配的算法。
-------等等,看得頭大?那么請(qǐng)看下面的版本:
通過(guò)數(shù)代人的努力,你終于趕上了剩男剩女的大潮,假設(shè)你是一位光榮的新世紀(jì)媒人,在你的手上有N個(gè)剩男,M個(gè)剩女,每個(gè)人都可能對(duì)多名異性有好感(-_-||暫時(shí)不考慮特殊的性取向),如果一對(duì)男女互有好感,那么你就可以把這一對(duì)撮合在一起,現(xiàn)在讓我們無(wú)視掉所有的單相思(好憂傷的感覺(jué)),你擁有的大概就是下面這樣一張關(guān)系圖,每一條連線都表示互有好感。
本著救人一命,勝造七級(jí)浮屠的原則,你想要盡可能地撮合更多的情侶,匈牙利算法的工作模式會(huì)教你這樣做:
一: 先試著給1號(hào)男生找妹子,發(fā)現(xiàn)第一個(gè)和他相連的1號(hào)女生還名花無(wú)主,got it,連上一條藍(lán)線
二:接著給2號(hào)男生找妹子,發(fā)現(xiàn)第一個(gè)和他相連的2號(hào)女生名花無(wú)主,got it
三:接下來(lái)是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è)遞歸的過(guò)程)
此時(shí)發(fā)現(xiàn)2號(hào)男生還能找到3號(hào)女生,那么之前的問(wèn)題迎刃而解了,回溯回去
2號(hào)男生可以找3號(hào)妹子~~~ 1號(hào)男生可以找2號(hào)妹子了~~~ 3號(hào)男生可以找1號(hào)妹子
所以第三步最后的結(jié)果就是:
四: 接下來(lái)是4號(hào)男生,很遺憾,按照第三步的節(jié)奏我們沒(méi)法給4號(hào)男生騰出來(lái)一個(gè)妹子,我們實(shí)在是無(wú)能為力了……香吉士同學(xué)走好。
這就是匈牙利算法的流程,其中找妹子是個(gè)遞歸的過(guò)程,最最關(guān)鍵的字就是“ 騰”字
其原則大概是:有機(jī)會(huì)上,沒(méi)機(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) //如果有曖昧并且還沒(méi)有標(biāo)記過(guò)(這里標(biāo)記的意思是這次查找曾試圖改變過(guò)該妹子的歸屬問(wèn)題,但是沒(méi)有成功,所以就不用瞎費(fèi)工夫了) { used[j]=1; if (girl[j]==0 || find(girl[j])) { //名花無(wú)主或者能騰出個(gè)位置來(lái),這里使用遞歸 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-03C語(yǔ)言大小端字節(jié)序存儲(chǔ)模式深入解讀
我們知道,當(dāng)編譯器執(zhí)行 “創(chuàng)建變量” 這一代碼時(shí),會(huì)在內(nèi)存中開(kāi)辟空間相應(yīng)的空間來(lái)存儲(chǔ)變量值。而對(duì)于整型變量而言,變量值又是以二進(jìn)制補(bǔ)碼的形式存放的2022-09-09QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn)
本文主要介紹了QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06C語(yǔ)言控制臺(tái)實(shí)現(xiàn)打飛機(jī)小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言控制臺(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ì)象,通過(guò)它可以訪問(wèn)當(dāng)前對(duì)象的所有成員,下面這篇文章主要給大家介紹了關(guān)于C++學(xué)習(xí)進(jìn)階篇之類大小計(jì)算和this指針的相關(guān)資料,需要的朋友可以參考下2023-04-04C++二叉搜索樹(shù)模擬實(shí)現(xiàn)示例
本文主要介紹了C++二叉搜索樹(shù)模擬實(shí)現(xiàn)示例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-11-11