欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++ 匈牙利算法案例分析詳解

 更新時(shí)間:2021年08月25日 17:30:41   作者:cillyb  
這篇文章主要介紹了C++ 匈牙利算法案例分析詳解,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

匈牙利算法是由匈牙利數(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語言編寫多功能日歷

    C語言編寫多功能日歷

    之前看到本站給大家分享了一則C語言實(shí)現(xiàn)的簡(jiǎn)單日歷,就手癢了,也想自己寫一個(gè),既然有簡(jiǎn)單了,那咱寫個(gè)稍微復(fù)雜點(diǎn)的,多功能的吧。呵呵,玩笑玩笑
    2015-03-03
  • C++實(shí)現(xiàn)教職工信息管理系統(tǒng)

    C++實(shí)現(xiàn)教職工信息管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)教職工信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • C語言大小端字節(jié)序存儲(chǔ)模式深入解讀

    C語言大小端字節(jié)序存儲(chǔ)模式深入解讀

    我們知道,當(dāng)編譯器執(zhí)行 “創(chuàng)建變量” 這一代碼時(shí),會(huì)在內(nèi)存中開辟空間相應(yīng)的空間來存儲(chǔ)變量值。而對(duì)于整型變量而言,變量值又是以二進(jìn)制補(bǔ)碼的形式存放的
    2022-09-09
  • QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn)

    QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn)

    本文主要介紹了QT中刪除信號(hào)于槽的連接的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-06-06
  • 淺析VC++中的頭文件包含問題

    淺析VC++中的頭文件包含問題

    類中盡量采用指針或引用方式調(diào)用其它類,這樣就可以只聲明class xxx了。并且這也符合資源最優(yōu)利用,更利于使用多態(tài)
    2013-09-09
  • C語言控制臺(tái)實(shí)現(xiàn)打飛機(jī)小游戲

    C語言控制臺(tái)實(shí)現(xiàn)打飛機(jī)小游戲

    這篇文章主要為大家詳細(xì)介紹了C語言控制臺(tái)實(shí)現(xiàn)打飛機(jī)小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-04-04
  • 詳解C++函數(shù)模板與分離編譯模式

    詳解C++函數(shù)模板與分離編譯模式

    這篇文章主要介紹了詳解C++函數(shù)模板與分離編譯模式的相關(guān)資料,幫助大家更好的理解和學(xué)習(xí)c++,感興趣的朋友可以了解下
    2020-08-08
  • C++學(xué)習(xí)進(jìn)階篇之類大小計(jì)算和this指針

    C++學(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
  • C++二叉搜索樹模擬實(shí)現(xiàn)示例

    C++二叉搜索樹模擬實(shí)現(xiàn)示例

    本文主要介紹了C++二叉搜索樹模擬實(shí)現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-11-11
  • c語言求1+2+...+n的解決方法

    c語言求1+2+...+n的解決方法

    本篇文章是對(duì)在c語言中求1+2+...+n的解決方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05

最新評(píng)論