algorithm - 为什么我们要在 Hopcroft-Karp 算法中寻找最短增广路径？

Question

在最大二分匹配的Hopcroft-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(√|V|)，对于 O(|E| √|V|) 步运行时间。