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

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

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

匈牙利算法是由匈牙利數(shù)學家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性證明的思想,它是部圖匹配最常見的算法,該算法的核心就是尋找增廣路徑,它是一種用增廣路徑求二分圖最大匹配的算法。

-------等等,看得頭大?那么請看下面的版本:

通過數(shù)代人的努力,你終于趕上了剩男剩女的大潮,假設你是一位光榮的新世紀媒人,在你的手上有N個剩男,M個剩女,每個人都可能對多名異性有好感(-_-||暫時不考慮特殊的性取向),如果一對男女互有好感,那么你就可以把這一對撮合在一起,現(xiàn)在讓我們無視掉所有的單相思(好憂傷的感覺),你擁有的大概就是下面這樣一張關(guān)系圖,每一條連線都表示互有好感。

本著救人一命,勝造七級浮屠的原則,你想要盡可能地撮合更多的情侶,匈牙利算法的工作模式會教你這樣做:

一: 先試著給1號男生找妹子,發(fā)現(xiàn)第一個和他相連的1號女生還名花無主,got it,連上一條藍線

二:接著給2號男生找妹子,發(fā)現(xiàn)第一個和他相連的2號女生名花無主,got it

三:接下來是3號男生,很遺憾1號女生已經(jīng)有主了,怎么辦呢?

我們試著給之前1號女生匹配的男生(也就是1號男生)另外分配一個妹子。

(黃色表示這條邊被臨時拆掉)

與1號男生相連的第二個女生是2號女生,但是2號女生也有主了,怎么辦呢?我們再試著給2號女生的原配重新找個妹子(注意這個步驟和上面是一樣的,這是一個遞歸的過程)

此時發(fā)現(xiàn)2號男生還能找到3號女生,那么之前的問題迎刃而解了,回溯回去

2號男生可以找3號妹子~~~                  1號男生可以找2號妹子了~~~                3號男生可以找1號妹子

所以第三步最后的結(jié)果就是:

四: 接下來是4號男生,很遺憾,按照第三步的節(jié)奏我們沒法給4號男生騰出來一個妹子,我們實在是無能為力了……香吉士同學走好。

這就是匈牙利算法的流程,其中找妹子是個遞歸的過程,最最關(guān)鍵的字就是“ 騰”字

其原則大概是:有機會上,沒機會創(chuàng)造機會也要上

bool find(int x){  
    int i,j;  
    for (j=1;j<=m;j++){    //掃描每個妹子  
        if (line[x][j]==true && used[j]==false)        
        //如果有曖昧并且還沒有標記過(這里標記的意思是這次查找曾試圖改變過該妹子的歸屬問題,但是沒有成功,所以就不用瞎費工夫了)  
        {  
            used[j]=1;  
            if (girl[j]==0 || find(girl[j])) {   
                //名花無主或者能騰出個位置來,這里使用遞歸  
                girl[j]=x;  
                return true;  
            }  
        }  
    }  
    return false;  
}  

在主程序我們這樣做:每一步相當于我們上面描述的一二三四中的一步

for (i=1;i<=n;i++)  
{  
    memset(used,0,sizeof(used));    //這個在每一步中清空  
    if find(i) all+=1;  
}

到此這篇關(guān)于C++ 匈牙利算法案例分析詳解的文章就介紹到這了,更多相關(guān)C++ 匈牙利算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言編寫多功能日歷

    C語言編寫多功能日歷

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

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

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

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

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

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

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

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

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

    C語言控制臺實現(xiàn)打飛機小游戲

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

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

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

    C++學習進階篇之類大小計算和this指針

    this是C++中的一個關(guān)鍵字,也是一個const指針,它指向當前對象,通過它可以訪問當前對象的所有成員,下面這篇文章主要給大家介紹了關(guān)于C++學習進階篇之類大小計算和this指針的相關(guān)資料,需要的朋友可以參考下
    2023-04-04
  • C++二叉搜索樹模擬實現(xiàn)示例

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

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

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

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

最新評論