電子發(fā)燒友App
描述
最近在做特征級別的感知結(jié)果融合算法。我的工作目的，是要將多種不同傳感器的感知結(jié)果，通過一定的機(jī)制融合起來，得到融合后的感知結(jié)果。
為此看了一些資料，了解到Apollo中使用了匈牙利匹配算法，之前不懂就學(xué)習(xí)了一下。
創(chuàng)建ROS工作環(huán)境
匈牙利算法（Hungarian Algorithm），該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法，是一種能夠在多項式時間內(nèi)解決分配問題的組合優(yōu)化算法。
網(wǎng)上有些作者比喻得很貼切，一句話先簡單理解下匈牙利算法吧：有100個男人和100個女人，使用匈牙利算法可以湊出更多的夫妻（一男一女…）。
為了更深的理解算法是如何運(yùn)行的，我們需要補(bǔ)充一些圖論知識：比如，什么是二分圖，什么又是增廣矩陣，等等。（圖論中非相關(guān)知識自行學(xué)習(xí)）
二、算法所需的圖論知識
二分圖
一個圖中的所有頂點(diǎn)可劃分為兩個不相交的集合 U 和 V ，使得每一條邊都分別連接U、V中的頂點(diǎn)。如果存在這樣的劃分，則此圖為一個二分圖，又稱二部圖。
“這個二分圖可以理解為某個世界，在該世界中人非男即女。那么每個人其實都是這個圖中的一個頂點(diǎn)，男人集合和女人集合彼此割裂，男人就是男人，女人就是女人，男人可以和女人結(jié)合，這實際上就是一個二分圖?！?/p>
匹配
二分圖中的一個匹配，就是此時二分圖中一些邊的集合，這個邊集合中的任意兩條邊沒有公共的頂點(diǎn)，也構(gòu)不成一個圈。
“100個男人和100個女人組成的二分圖中，如果可以任意結(jié)婚，那么就會有很多種結(jié)婚組合。我們把其中的一種結(jié)婚組合的可能性，稱為一次匹配。在這次匹配中，任意一對夫妻都是合法夫妻，沒有任何性別的第三者存在哈哈?！?/p>
最大匹配
一個圖的所有匹配中，所含匹配邊數(shù)最多的匹配，稱為這個圖的最大匹配。最大匹配數(shù)，就是最大匹配時邊的數(shù)目。
“100個男人和100個女人，在平行時空下肯定有很多種結(jié)婚的組合啊，也就是有很多種匹配。
那么，在所有匹配中，結(jié)婚對數(shù)最多的那次匹配，就是這個二分圖的最大匹配。匈牙利算法是個月老和丘比特，他的目標(biāo)就是要湊出最多的新人”
完美匹配
如果一個圖的某個匹配中，所有的頂點(diǎn)都是匹配點(diǎn)，那么它就是一個完美匹配。
顯然，完美匹配一定是最大匹配（完美匹配的任何一個點(diǎn)都已經(jīng)匹配，添加一條新的匹配邊一定會與已有的匹配邊沖突）。但并非每個圖都存在完美匹配。
“100個男人和100個女人，每個男人都和一個女人結(jié)婚了，而且他們都是沒有重婚罪的合法夫妻，這就是這個圖的完美匹配。顯然，這是一次最大匹配了。
如果100個男人和99個女人構(gòu)成的二分圖，即使匈牙利算法再厲害，也還是會有個單身狗，并不存在完美匹配?！?/p>
三、算法原理
匈牙利算法有兩個重要概念，先介紹一下。
交錯路徑
給定圖G的一個匹配M，如果一條路徑的邊交替出現(xiàn)在M中和不出現(xiàn)在M中，我們稱之為一條M-交錯路徑。
增廣路徑
如果一條M-交錯路徑，它的兩個端點(diǎn)都不與M中的邊關(guān)聯(lián)，我們稱這條路徑叫做M-增廣路徑。增廣路徑有一個重要特點(diǎn)：非匹配邊比匹配邊多一條。
我畫了一幅圖，我們有一幅8個頂點(diǎn)構(gòu)成的圖G。其中有一種匹配，是圖中的黑線表示的2和4兩條邊，這兩條邊加上8個頂點(diǎn)，構(gòu)成了圖G的一種匹配M。
為了方便理解，我將圖中的8個頂點(diǎn)按照二分圖進(jìn)行劃分，綠色點(diǎn)表示男人，黃色點(diǎn)表示女人。
顯然匹配M的意思就是，8個人中，由邊2和邊4代表的兩對男女結(jié)成了夫妻。
按照交錯路徑的概念，1234、2345、12345都是M-交錯路徑（123456都不是，因為5和6均不在匹配M中，01234同理），而在這三個交錯路徑中，只有12345才是M-增廣路徑。那么，找出匹配M的增廣路徑意義合在呢？
我們會發(fā)現(xiàn)，在路徑12345中，還存在著另外一種匹配1、3、5，它的匹配數(shù)是3，要大于匹配M的匹配數(shù)2。
那么我們就得到了新的一個匹配N，它比匹配M更優(yōu)。按照同樣的方式，我們來尋找N-增廣路徑，會發(fā)現(xiàn)0123456是匹配N的增廣路徑，它的匹配數(shù)是4。
因此圖G的最大匹配，實際上是由0、2、4、6等四條邊構(gòu)成的匹配。
因此，研究增廣路徑的意義就是改進(jìn)匹配模式，只要把增廣路徑中的匹配邊和非匹配邊的身份交換就可以了。身份交換后，圖中的匹配邊數(shù)目，將比原來增多 1 條。
匈牙利算法的核心，就是通過不斷尋找原有匹配M的增廣路徑，來增加匹配中的匹配邊和匹配點(diǎn)，從而達(dá)到該圖下的最大匹配。
四、算法流程
概念
飽和
設(shè)一個圖為G，G中一些不相鄰的邊組成了一個集合M，這個集合M就是G的一個匹配。匹配M中的每條邊都有兩個端點(diǎn)，這兩個端點(diǎn)都稱為是M飽和的。
“有一些男人一些女人婚姻關(guān)系未明（一個圖G），一些男女結(jié)成了夫妻（一種匹配關(guān)系M），結(jié)婚的男女都算已婚了（M飽和）”
綜上，就把飽和——理解成已婚，比較好理解我下面的分析。
4.1 匈牙利算法單邊飽和
第0步
10個男人，9個女人，怎么飽和？如果10個男人，有10個及以上的女人，存在飽和的可能性，任選一種匹配M，準(zhǔn)備去找一個飽和X匹配。
第1步
如果當(dāng)前匹配M，已經(jīng)X飽和了，10個男人都匹配了老婆，算法停止；否則，任取一個沒老婆的男人x（取X中一個M非飽和點(diǎn)x），這個男人放進(jìn)集合S中，并設(shè)一個集合T為空集。
集合S中會存儲已經(jīng)結(jié)婚的男人+這個單身狗，集合T是這些男人的已婚配偶。
第2步
如果集合S中的位于匹配頂點(diǎn)的男人，他們可以匹配的女人（頂點(diǎn)的臨接頂點(diǎn)N(S)），全部是已婚配偶（∈T），那么算法停止，當(dāng)前的圖就是會有男人找不到老婆。
否則，我們找到了一個沒有在當(dāng)前路徑的女人y（y∈N(S)-T），當(dāng)然了這個女人可能有老公（也在匹配M中，只不過是不同路徑），也有可能是硬拆散的（算法首次進(jìn)入第2步，由于集合T為空，會強(qiáng)拆掉一組夫妻），也有可能壓根就是未婚的。
第3步
如果上一步選擇的女人y，她是有老公z的（y是M飽和的，yz∈M）。我們暫時先把他們拆開，老公z放進(jìn)集合S中，女人y放進(jìn)集合T中，然后去執(zhí)行第2步。
去執(zhí)行第2步，意味著也許也許也許…拆掉現(xiàn)有的一對夫妻，這對夫妻中的老婆能解決之前狼少肉多問題的同時，老公還能找到新的老婆。
否則，如果上一步選擇的女人y，是沒有老公的。我們找到了新的一種結(jié)婚方案（一條增廣路P(x,y)），這個方案里讓單身狗x去娶一個已婚的女人，然后原匹配夫妻中每個已婚男人都去娶別人老婆，剩下的一個已婚男人去娶這個小姑娘y。大家都很happy……h(huán)ahahaha（增廣路取反）
4.2 二部圖最大匹配的匈牙利算法
這里可以自行按照上面的分析，去理解算法。雖然真正理解算法較為困難，也不再這里贅述。
總結(jié)
這篇文章清晰明了的介紹了下匈牙利算法。如何與多傳感器融合特征算法相結(jié)合，會在以后的文章中介紹。
審核編輯：劉清
工商網(wǎng)監(jiān)
評論