在最大二部匹配的HoprFot卡普算法中,为什么我们总是在广度优先搜索中寻找最短的增广路径?是不是因为广度优先搜索总是找到最短的路径我只是不明白为什么增广路径最短很重要。

最佳答案

只找到一条增强路径已经是θ(e)时间运算。Hopcroft-Karp(实际上,如果有人稍微斜视一下,大多数增强路径算法)背后的想法是对每个θ(| E |)时间迭代做更多的工作。
为什么是最短扩充路径?H–K同时查找多条增强路径,这些路径必须是顶点不相交的,才能同时使用顶点不相交产生了一个包装问题,贪婪的解决方案是先包装“最密集”(最佳值与空间比)的东西,即最短的扩充路径。在实践中,贪婪算法通常工作得很好(例如,见集合覆盖分析,或随机图上的h–k)。
然而,真正的答案是H–K比θ(E | V |)好得多H-K的形式化分析使用最短增强路径的长度来测量算法的进展,并且通过使用这些路径的最大集合,H-K增加了该量。当最短增广路径达到长度√v时,不可能包含超过√v的路径(顶点不相交),因此该算法最多有√v边可走,迭代总数为o(√v),对于o(e√v)-步长运行时间。

09-25 22:30
查看更多