二部圖系列視頻

關(guān)于匈牙利匹配可以聯(lián)系下面兩篇博客更容易理解和補(bǔ)盲：
帶你入門多目標(biāo)跟蹤（三）匈牙利算法&KM算法
趣寫算法系列之–匈牙利算法

14.1 二部圖

廣度優(yōu)先搜索
廣度優(yōu)先，可以使用隊(duì)列來操作:

• 依次遍歷節(jié)點(diǎn)，首先遍歷第一個(gè)節(jié)點(diǎn)A，判斷節(jié)點(diǎn)A是否遍歷過，如果節(jié)點(diǎn)A沒有遍歷過，就把節(jié)點(diǎn)A添加進(jìn)隊(duì)列。
• 然后取出隊(duì)列中的第一個(gè)元素A，對于和節(jié)點(diǎn)A連接的某節(jié)點(diǎn)B和節(jié)點(diǎn)C等，把節(jié)點(diǎn)B和c進(jìn)行標(biāo)記(標(biāo)記就是根據(jù)題目的具體要求進(jìn)行操作，即你的目的是什么你就干什么），并且如果節(jié)點(diǎn)B和c沒有遍歷過，那么把節(jié)點(diǎn)B和C添加進(jìn)隊(duì)列。
• 然后再取出隊(duì)列中的第一個(gè)元素，就是節(jié)點(diǎn)B，遍歷到了B節(jié)點(diǎn)，再對和B節(jié)點(diǎn)連接的節(jié)點(diǎn)D進(jìn)行標(biāo)記，并且判斷D是否遍歷過，沒有遍歷過的話就添加到隊(duì)列。
• 然后再取出隊(duì)列第一個(gè)元素，為節(jié)點(diǎn)C。以此類推

14.2 無權(quán)二部圖的最大匹配，最大流問題，其中有個(gè)網(wǎng)絡(luò)最大流方法，貪心算法找最大匹配可能會(huì)失敗。
貪心算法，每次局部最優(yōu)，得到全局最優(yōu)。
例如，每次只能從錢箱子里面取一張鈔票，那肯定是每次都拿里面面值最大的一張，這樣就會(huì)得到最優(yōu)結(jié)果。
無權(quán)二部圖的每條邊權(quán)重都是一樣的，為1。無權(quán)并不是說權(quán)重為0。

14.3有權(quán)二部圖的最大匹配和最小匹配，把圖邊制作一個(gè)鄰接矩陣。我們的目標(biāo)是尋找權(quán)重之和最大的匹配。最大匹配限制條件:每一個(gè)節(jié)點(diǎn)都只能擁有一條邊。注意，二部圖并不是每個(gè)節(jié)點(diǎn)只有一條邊。
以寵物收養(yǎng)為例，有權(quán)二部圖的邊的權(quán)重表示人對寵物的喜好程度，沒有邊表示喜好程度是0，也就是完全不喜歡。
寵物收養(yǎng)機(jī)構(gòu)應(yīng)該尋找有權(quán)二部圖中的最大匹配。最大匹配，意味著讓人領(lǐng)養(yǎng)最喜歡的寵物，獲得最大的幸福感。

對于有權(quán)圖，最大匹配和最小匹配是可以相互轉(zhuǎn)化的。只需要把所有權(quán)重乘以$?1$全都變?yōu)樨?fù)數(shù)即可。即，本來求最大值，最大值乘以 $?1$ 就變成了最小值了。

最大匹配是最優(yōu)匹配，即所有匹配權(quán)重之和(函數(shù)值）最大。
最小匹配也是最優(yōu)匹配，即所有匹配權(quán)重之和(函數(shù)值）最小。

• 最大匹配可以理解為人對物體的喜好程度，每個(gè)人對分配給他的物體的喜好的和值最大的匹配對，就是最大匹配；
• 最小匹配可以理解為兩種物體的差異，所有物體差異的和值最小，就是最小匹配。

匈牙利算法用來尋找有權(quán)二部圖中的最小匹配。但是匈牙利匹配中有一個(gè)限制，就是兩個(gè)集合中的節(jié)點(diǎn)數(shù)都一樣為n，即鄰接矩陣必須是一個(gè) $n?n$ 的方陣。匈牙利算法的時(shí)間復(fù)雜度是 $n^3$。

問：匈牙利算法的輸入必須要是方陣嗎，也就是左右數(shù)目一樣嗎？

答：匈牙利算法不需要，KM算法必須得是完全匹配（可以補(bǔ)權(quán)值為零的邊得到）。
但是在自動(dòng)駕駛中，一般直接用匈牙利算法代指KM算法，里面調(diào)用的就是KM算法。
所以，自動(dòng)駕駛中指代額匈牙利算法，是一個(gè)方陣n*n。如果有一條邊權(quán)值為0，就表示二者沒有邊。
所以，如果匈牙利算法+KM算法最終得到的二者匹配的一對，如果邊的權(quán)重為0，就表示不匹配。并不表示強(qiáng)行把二者給匹配起來。

匈牙利算法是解決最小匹配的問題，但是我們實(shí)際問題如果是要求最大匹配，應(yīng)該怎么辦呢？我們可以把最大匹配等價(jià)轉(zhuǎn)換為最小匹配，即，把權(quán)重全部取反，這樣就把喜愛程度變成厭惡程度了，然后再調(diào)用匈牙利算法即可。
最小匹配的理解就是幸福度最低，我們最開始是$+10$，表示特別喜歡某只寵物，取負(fù)數(shù)就變成了特別不喜歡這只寵物，如果每個(gè)人都分配到了最最不喜歡的寵物，那么就是最小匹配。所以最小匹配并不是說被領(lǐng)養(yǎng)的寵物最少，而是最差匹配。最大匹配應(yīng)該理解為最優(yōu)匹配，最小匹配應(yīng)該理解為最差匹配。

不過，不要狹隘的理解最大匹配和最小匹配的匹配結(jié)果是一樣的。因?yàn)樽畲笃ヅ涫菣?quán)值之和最大的匹配，而最小匹配是權(quán)值之和最小的匹配。兩個(gè)集合中，最大匹配和最小匹配肯定不會(huì)是同一種匹配結(jié)果。前面介紹的最大匹配和最小匹配的互相轉(zhuǎn)化，最終的匹配結(jié)果是同一種，只不過因?yàn)樽钚』菀浊蠼?#xff0c;例如匈牙利匹配就是根據(jù)尋找權(quán)重之和的最小值來求解問題的。

【14-4: 匈牙利算法 Hungarian Algorithm-嗶哩嗶哩】

匈牙利算法只需要操作鄰接矩陣

最大匹配并不唯一，可能有多種匹配方式都能達(dá)到同樣幸福度。

14.6 穩(wěn)定婚配問題
Gale-shapley解決穩(wěn)定婚配問題。就是$n$個(gè)男人分別對$n$個(gè)女人進(jìn)行愛慕程度排序，$n$個(gè)女人也分別對$n$個(gè)男人進(jìn)行愛慕程度排序。
每個(gè)男性都首先選擇最喜歡的女性，如果女性的愛慕程度的最優(yōu)選擇不是你，你就劃掉該女性，下次匹配不會(huì)再考慮她，然后你再選擇你第二愛慕的女性，直到配對成功。并且每次匹配之后，依舊單身的男性先選擇女性，無論女性是否已配對，可以挖墻腳，把已配對的男性變成單身。直到最后所有男人配對成功(此時(shí)所有女人也會(huì)配對成功)。

總結(jié)

以上是生活随笔為你收集整理的【数学与算法】二部图、匈牙利匹配、稳定婚配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。