二分图的最优匹配（KM算法）.doc

二分图的最优匹配（KM 算法） KM 算法是解决最大权匹配问题的经典算法，在二分图中寻找最大权匹配的问题。该算法的基本原理是通过给每个顶点一个标号（称做顶标）来把求最大权匹配的问题转化为求完备匹配的问题。 KM 算法的正确性基于以下定理：若由二分图中所有满足 A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 KM 算法的实现过程可以分为以下几步： 1. 初始化可行顶标的值，令 A[ i ]为所有与顶点 Xi 关联的边的最大权，B[j]=0。 2. 用匈牙利算法寻找完备匹配。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 3. 如果当前相等子图没有完备匹配，我们求当前相等子图的完备匹配失败了，是因为对于某个 X 顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是 X 顶点。现在我们把交错树中 X 顶点的顶标全都减小某个值 d，Y 顶点的顶标全都增加同一个值 d，以扩大相等子图。 4. 重复步骤 2 和 3 直到找到相等子图的完备匹配为止。 在 KM 算法的实现过程中，我们需要计算 d 的值，以使 A[ i ]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图。d 的计算方法是：d = Min{A[i]+B[j]-w[i,j] | Xi 在交错树中，Yi 不在交错树中}。 KM 算法的时间复杂度可以做到 O(n3)，这是因为我们可以使用松弛量函数 slack 来优化算法的实现。在寻找增广路的过程中，我们可以初始化每个 Y 顶点的松弛量函数 slack 为无穷大，然后在检查边(i,j)时，如果它不在相等子图中，则让 slack[j]变成原值与 A[ i ]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的 Y 顶点的 slack 值中的最小值作为 d 值即可。 KM 算法是解决最大权匹配问题的经典算法，通过给每个顶点一个标号来把求最大权匹配的问题转化为求完备匹配的问题。其正确性基于相等子图的完备匹配定理，并且可以通过优化实现来达到 O(n3) 的时间复杂度。