爲什麼我們在Hopcroft-Karp算法中尋找最短的增廣路徑？

Question

在Hopfroft-Karp最大二分匹配算法中，爲什麼我們總是在寬度優先搜索中尋找最短增廣路徑？是因爲廣度優先搜索總是找到最短路徑？我只是困惑爲什麼擴張路徑最短是很重要的。

Answer 1

找到一條增強路徑已經是Theta（| E |）時間操作。 Hopcroft-Karp背後的想法（大多數增廣路徑算法，實際上，如果稍微眯起一點）就是在每個Theta（| E |）時間迭代中做更多的事情。

爲什麼最短的增廣路徑？ H-K一次尋找幾條擴充路徑，它們必須是頂點不相交才能同時有用。頂點不相交產生了一個打包問題，貪婪的解決方案是首先打包「最密集的」（最佳值與空間比）事物，即最短的增廣路徑。在實踐中，貪婪算法通常效果很好（例如，參見集合覆蓋分析或隨機圖上的H-K）。

但真正的答案是H-K比Theta（| E | | V |）好得多。 H-K的形式分析使用最短增廣路徑的長度來衡量算法的進度，並且通過使用這些路徑的最大集合，H-K增加了這個數量。當最短增廣路徑達到長度√| V |時，不可能打包超過√| V | （頂點不相交），所以算法至多有√| V |對於一個O（| E |√| V |）階段的運行時間，迭代的總次數爲O（√| V |）。