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|) 步。