今天是算法與數(shù)據(jù)結(jié)構(gòu)專題的第31篇文章，我們一起來聊聊二分圖匹配與匈牙利算法。
在上一篇文章當(dāng)中我們介紹了一個有趣的穩(wěn)定婚姻問題，模擬了男男女女配對的婚戀場景，并且研究了一下讓匹配更加穩(wěn)定的Gale-Shapley算法。如果錯過了這篇文章的同學(xué)可以從下方的傳送門回顧一下婚姻穩(wěn)定問題的具體內(nèi)容。
學(xué)算法還能指導(dǎo)找對象？是的，這就是大名鼎鼎的穩(wěn)定婚姻算法?mp.weixin.qq.com
在上一篇文章的末尾我們曾經(jīng)提到過，婚姻匹配問題本質(zhì)上來說其實(shí)是二分圖匹配的問題。那么什么又是二分圖匹配呢？二分圖匹配的問題又該通過什么算法來解決呢？下面就讓我們一起從最基礎(chǔ)的概念開始。
二分圖匹配
二分圖的概念很簡單，就是在一個無向圖當(dāng)中，所有的點(diǎn)可以分成兩個子集。這兩個子集當(dāng)中的點(diǎn)各自互不相交，并且圖當(dāng)中的所有邊關(guān)聯(lián)的頂點(diǎn)都屬于兩個不同的集合。單純用語言描述有一點(diǎn)吃力，其實(shí)我們找一張圖看一下就明白了。
在上圖當(dāng)中很明顯左邊的豎著的三個點(diǎn)是一個集合，右邊豎著的三個點(diǎn)是另外一個集合。兩個集合之間有邊相連，集合內(nèi)部互不連通。
匹配與最大匹配
在二分圖當(dāng)中，如果我們選擇了一條邊就會連通對應(yīng)的兩個點(diǎn)。這也就構(gòu)成了一個匹配，我們規(guī)定一個頂點(diǎn)最多只能構(gòu)成一個匹配，也就是說所有的匹配之間沒有公共的點(diǎn)。
對于一張二分圖而言，構(gòu)成的匹配數(shù)量可以是不同的，其中匹配數(shù)量最多的情況叫做最大匹配。如果所有頂點(diǎn)都有了匹配，那么就稱這種情況為完美匹配。
今天要介紹的匈牙利算法就是一種用來完成二分圖最大匹配的算法。
匈牙利算法
匈牙利我們都知道是一個國家的名字，這和算法的發(fā)明人有關(guān)。匈牙利算法的發(fā)明人Edmonds在1965年提出了匈牙利算法，我也不知道為什么算法發(fā)明人是匈牙利的就叫匈牙利算法，也沒見過其他以國家命名的算法，是因為匈牙利人提出的算法太少了嗎？
匈牙利算法的核心原理非常簡單，就是尋找增廣路徑，從而達(dá)成最大匹配。
我們用通俗易懂的語言來解釋一下算法的含義，我們還用上面那張圖作為舉例。我們首先將左邊的1和右側(cè)的a，左邊的2和右側(cè)的b節(jié)點(diǎn)匹配。
這樣當(dāng)我們想要匹配左側(cè)的3號節(jié)點(diǎn)的時候發(fā)現(xiàn)了一個問題，那就是能夠和3號節(jié)點(diǎn)構(gòu)成匹配的a和b節(jié)點(diǎn)都已經(jīng)被占據(jù)了。所以3號節(jié)點(diǎn)無法構(gòu)成匹配，但是我們觀察一下圖就能發(fā)現(xiàn)，如果1和2號節(jié)點(diǎn)稍微調(diào)整一下匹配的情況，其實(shí)是可以給3號節(jié)點(diǎn)挪出一個位置來的。
具體怎么操作呢？
我們遍歷3號節(jié)點(diǎn)能夠匹配的節(jié)點(diǎn)，首先找到a節(jié)點(diǎn)，發(fā)現(xiàn)a節(jié)點(diǎn)已經(jīng)被占用了。于是我們找到a節(jié)點(diǎn)匹配的節(jié)點(diǎn)也就是1號節(jié)點(diǎn)，試著讓它重新找一個匹配，給3號節(jié)點(diǎn)挪出位置來。于是我們遞歸安排1號節(jié)點(diǎn)，我們遍歷到b節(jié)點(diǎn)，發(fā)現(xiàn)b節(jié)點(diǎn)也被占用了。于是我們同樣遞歸與b節(jié)點(diǎn)匹配的2號節(jié)點(diǎn)，看看2號節(jié)點(diǎn)能不能找到新的坑騰出一個位置來。
我們觀察一下發(fā)現(xiàn)2號節(jié)點(diǎn)可以和c節(jié)點(diǎn)構(gòu)成匹配，騰出位置來給1號，這樣1號就能騰出位置來給3號節(jié)點(diǎn)了。所以最終的匹配結(jié)果就成了這樣：
其中藍(lán)線是調(diào)整匹配之前的結(jié)果，紅色是調(diào)整之后的結(jié)果。
本質(zhì)上來說，匈牙利算法就是一個調(diào)整匹配的過程。通過遞歸調(diào)用的形式去嘗試調(diào)整已經(jīng)占據(jù)了發(fā)生沖突位置的匹配，騰出位置來給右面的節(jié)點(diǎn)。
我們把匈牙利算法的原理和Gale-Shapley算法比較一下，有沒有發(fā)現(xiàn)什么？其實(shí)這兩個算法的核心原理是一樣的，在GS算法當(dāng)中我們是先由男生發(fā)起追求，盡可能構(gòu)成匹配。然后單身的男生再一輪一輪發(fā)起表白，如果有更好的匹配則斷開之前的匹配。在穩(wěn)定婚姻問題當(dāng)中我們定義了匹配的好壞，而在原生的二分圖匹配的問題當(dāng)中匹配是不分好壞的。如果我們拋開匹配好壞不談，把優(yōu)質(zhì)男生搶占劣質(zhì)男生女朋友的過程看成是匹配調(diào)整的過程，那么其實(shí)這兩個算法的核心幾乎是一樣的。
唯一不同的是GS算法是一輪一輪的迭代，直到所有節(jié)點(diǎn)完成匹配為止。因為在婚姻匹配問題當(dāng)中是一定有完美匹配的解的，而二分圖匹配的問題當(dāng)中，完美匹配的情況可能不一定存在。所以我們不能使用這樣迭代的方式進(jìn)行，而使用遞歸進(jìn)行更好一些。換句話來說匈牙利算法研究的是二分圖匹配的通解，而GS算法只是二分圖算法的一個特殊案例。
代碼實(shí)現(xiàn)
匈牙利算法的思路如果學(xué)會了，代碼其實(shí)非常簡單，就是一個簡單的遞歸調(diào)用。
def find_match(x):
for i in range(n):
if graph[x][i] and not tried[i]:
tried[i] = True
if match[i] == -1 or find_match(match[i]):
match[i] = x
return True
return False
for i in range(n):
tried = [0 for _ in range(n)]
find_match(i)
我們再試著用匈牙利算法來做一下婚姻穩(wěn)定問題，因為在婚姻穩(wěn)定問題當(dāng)中每兩個異性之間都有配對的可能，所以不需要再判斷連通的情況了。并且構(gòu)成的匹配有質(zhì)量好壞的差別，所以需要去掉是否嘗試過的判斷。
girls_matched = [-1 for _ in range(n)]
boys_round = [0 for _ in range(n)]
boys_matched = [-1 for _ in range(n)]
def find_match(x):
for i in range(n):
idx = girls[i].index(x)
mate = girls_matched[i]
mate_id = n+1 if mate == -1 else girls[i].index(mate)
# 如果女孩i沒有對象或者是對象比x男生弱
if mate == -1 or (idx < mate_id and find_match(girls_matched[i])):
girls_matched[i] = x
boys_matched[x] = i
return True
return False
for i in range(n):
# 對i男生進(jìn)行匹配
find_match(i)
我們運(yùn)行一下這段代碼：
結(jié)果當(dāng)然是正確的，但是如果我們嘗試用GS算法演示一下會發(fā)現(xiàn)這兩個算法的結(jié)果不一樣。這是為什么呢？原因也很簡單，因為GS算法男生追求的順序是自己喜好的順序，而匈牙利算法當(dāng)中是按照編號順序，所以因此得到的結(jié)果不同。
總結(jié)
關(guān)于匈牙利算法的原理與介紹就到這里結(jié)束了，對于二分圖匹配問題來說我們有很多種算法可以解決，但是匈牙利算法是其中比較簡單易于理解與實(shí)現(xiàn)的一種。如果我們將它與之前介紹的GS算法相對比，可以發(fā)現(xiàn)很多共性和連通的部分。文中只是簡單介紹了一些，如果仔細(xì)研究下去還會發(fā)現(xiàn)很多有趣的點(diǎn)。
今天的文章到這里就結(jié)束了，如果喜歡本文的話，請來一波素質(zhì)三連，給我一點(diǎn)支持吧（關(guān)注、轉(zhuǎn)發(fā)、點(diǎn)贊）。
- END -
本文始發(fā)于公眾號： TechFlow
