匈牙利算法如何找最大匹配

匈牙利算法（Hungarian Algorithm）是一種用於解決二分圖最大匹配問題的算法。二分圖最大匹配問題是指在一個二分圖中找到最大數量的邊，使得每一邊的兩個頂點都不屬於同一個集合。在匈牙利算法中，二分圖通常表示為矩陣形式，其中每一行和每一列代表一個頂點，而矩陣的元素表示兩個頂點之間的權重或成本。

匈牙利算法的步驟如下：

1. 初始化：將原問題轉換為標準形式，即所有行和列的權重都為正數，且不存在兩行或兩列完全相同。如果存在負權重，可以通過將所有權重加上最大負權重來達到這一標準。

2. 減少：通過將行或列中的一個元素減少1，同時將另一個元素增加1，來減少矩陣中的元素。這樣可以找到一個更小的子問題，其最優解與原問題的最優解相同。

3. 消除：如果一個元素的值等於其所在行或列的其他所有元素的值，那麼這個元素所在的行或列可以被完全消除。

4. 補齊：如果一個元素的值比其所在行或列的其他所有元素的值都小，那麼這個元素可以被補齊到其所在行或列的其他元素的值。

5. 重複：重複減少、消除和補齊步驟，直到矩陣不能再進行這些操作。

6. 匹配：通過檢查矩陣中的"1"（表示匹配）和"0"（表示未匹配）來找到最大匹配。

7. 解的驗證：通過檢查匹配是否構成一個增廣路徑來驗證解是否最優。如果存在增廣路徑，那麼可以通過增加或減少一條邊來得到一個更大的匹配。

匈牙利算法的複雜度為O(n^3)，其中n是矩陣的大小。在實際套用中，可以通過一些最佳化技巧來減少計算量，例如使用動態規劃來避免重複計算。

需要注意的是，匈牙利算法只能解決二分圖最大匹配問題，對於非二分圖或其他類型的匹配問題，需要使用其他算法或方法。