二部圖系列視頻

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

14.1 二部圖

廣度優先搜索
廣度優先，可以使用隊列來操作:

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

14.2 無權二部圖的最大匹配，最大流問題，其中有個網絡最大流方法，貪心算法找最大匹配可能會失敗。
貪心算法，每次局部最優，得到全局最優。
例如，每次只能從錢箱子里面取一張鈔票，那肯定是每次都拿里面面值最大的一張，這樣就會得到最優結果。
無權二部圖的每條邊權重都是一樣的，為1。無權并不是說權重為0。

14.3有權二部圖的最大匹配和最小匹配，把圖邊制作一個鄰接矩陣。我們的目標是尋找權重之和最大的匹配。最大匹配限制條件:每一個節點都只能擁有一條邊。注意，二部圖并不是每個節點只有一條邊。
以寵物收養為例，有權二部圖的邊的權重表示人對寵物的喜好程度，沒有邊表示喜好程度是0，也就是完全不喜歡。
寵物收養機構應該尋找有權二部圖中的最大匹配。最大匹配，意味著讓人領養最喜歡的寵物，獲得最大的幸福感。

對于有權圖，最大匹配和最小匹配是可以相互轉化的。只需要把所有權重乘以$?1$全都變為負數即可。即，本來求最大值，最大值乘以 $?1$ 就變成了最小值了。

最大匹配是最優匹配，即所有匹配權重之和(函數值）最大。
最小匹配也是最優匹配，即所有匹配權重之和(函數值）最小。

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

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

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

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

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

不過，不要狹隘的理解最大匹配和最小匹配的匹配結果是一樣的。因為最大匹配是權值之和最大的匹配，而最小匹配是權值之和最小的匹配。兩個集合中，最大匹配和最小匹配肯定不會是同一種匹配結果。前面介紹的最大匹配和最小匹配的互相轉化，最終的匹配結果是同一種，只不過因為最小化更容易求解，例如匈牙利匹配就是根據尋找權重之和的最小值來求解問題的。

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

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

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

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

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。