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

二分图的最优匹配（KM算法）KM算法用来解决最大权匹配问题： 在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。基本原理该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A i ，顶点Yj的顶标为B j ，顶点Xi与Yj之间的边权为wi,j。在算法执行过程中的任一时刻，对于任一条边(i,j)，A i +Bj=wi,j始终成立。 KM算法的正确性基于以下定理： 若由二分图中所有满足A i +Bj=wi,j的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是 Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A i +Bj=wi,j恒成立，令A i 为所有与顶点Xi关联的边的最大权，Bj=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现： 1）两端都在交错树中的边(i,j)，A i +Bj的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 2）两端都不在交错树中的边(i,j)，A i 和Bj都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 3）X端不在交错树中，Y端在交错树中的边(i,j)，它的A i +Bj的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 4）X端在交错树中，Y端不在交错树中的边(i,j)，它的A i +Bj的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中x1-y4这条边）现在的问题就是求d值了。为了使A i +Bj=wi,j始终成立，且至少有一条边进入相等子图，d应该等于： MinAi+Bj-wi,j | Xi在交错树中，Yi不在交错树中。改进 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改 顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次 开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slackj变成原值与A i +Bj-wi,j的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d（因为：d的定义为 min (x,y)| Lx(x)+ Ly(y)- W(x,y), x S, yT （关键，关键），此时属于S的X均已经减去d了，所以不属于T的y也要减去d，防止下次循环更改出错）。 KuhnMunkras算法流程： (1)初始化可行顶标的值 (2)用匈牙利算法寻找完备匹配 (3)若未找到完备匹配则修改可行顶标的值 (4)重复(2)(3)直到找到相等子图的完备匹配为止例已知K5,5的权矩阵为y1 y2 y3 y4 y5x1 3 5 5 4 1x2 2 2 0 2 2x3 2 4 4 1 0x4 0 1 1 0 0x5 1 2 1 3 3求最佳匹配，其中K5,5的顶划分为X=xi,Y=yi,i=1,2,3,4,5.解：(1)取可行顶标l(v)为 l(yi)=0,i=1,2,3,4,5；l(x1)=max3,5,5,4,1=5,l(x2)=max2,2,0,2,2=2,l(x3)=max(2,4,4,1,0=4,l(x4)=max0,1,1,0,0=1,l(x5)=max1,2,1,3,3=3.(2) Gl及其上之匹配见图7.12。这个图中(G-x2)=3,由Tutte定理知无完备匹配。需要修改顶标。(3) u=x4,得S=x4,x3,x1,T=y3,y2,N(S)=T,于是al=min(l(x)+l(y)-w(xy)=1. (xS,yT)x1,x2,x3,x4,x5的顶标分别修改成4,2,3,0,3；y1,y2,y3,y4,y5的顶标分别修改成0,1,1,0,0。(4) 用修改后的顶标l得Gl及其上面的一个完备匹配如图7.13。图中粗实线给出了一个最佳匹配，其最大权是2+4+1+4+3=14。我们看出：al0；修改后的顶标仍是可行顶标；Gl中仍含Gl中的匹配M；Gl中至少会出现不属于M的一条边，所以会造成M的逐渐增广。得到可行顶标后求最大匹配：书上这部分没讲，实际上是这样的，对于上面这个例子来说，通过Kuhn-Munkres得到了顶标l(x)= 4,2,3,0,3,l(y)=0,1,1,0,0,那么，对于所有的l(xi)+l(yj) = w(i,j)，在二分图G设置存在边w(i,j)。再用匈牙利算法求出最大匹配，再把匹配中的每一边的权值加起来就是最后的结果了。 例2如图：| 1 2 3 | 3 2 4 | 2 3 5 |若要对这个完全二分图求最佳匹配初始化：Lx(1)= max y| w(1,y), 1= y Y 3- X 1。我们把寻找增广路径失败的 DFS 的交错树中，在 X 部顶点集称之为 S， 在 Y 部的顶点集称之为 T。则 S= 1, 2 ，T= 3 。现在我们就通过修改顶标值来扩大等价子图，如何修改。1) 我们寻找一个 d 值，使得 d= min (x,y)| Lx(x)+ Ly(y)- W(x,y), x S, yT ，因些，这时 d= minLx(1)+Ly(1)-W(1,1), Lx(1)+Ly(2)-W(1,2), Lx(2)+Ly(1)-W(2,1), Lx(2)+Ly(2)-W(2,2) =min 3+0- 1, 3+0-2, 4+0-3, 4+0-2 = min 2, 1, 1, 2 = 1。寻找最小的 d 是为了保证修改后仍满足性质对于边 有 Lx(x)+ Ly(y)= W(x,y)。2) 然后对于顶点 x1. 如果 x S 则 Lx(x)= Lx(x)- d。2. 如果 x T则 Ly(x)= Ly(x)+ d。3. 其它情况保持不变。如此修改后，我们发现对于边，顶标 Lx(x)+ Ly(y) 的值为1. Lx(x)- d+ Ly(y)+ d， x S, yT。2. Lx(x)+ Ly(y)，xS, yT。3. Lx(x)- d+ Ly(y)， x S, yT。4. Lx(x)+ Ly(y)+ d， xS, yT。易知，修改后对于任何边仍满足 Lx(x)+ Ly(y)= W(x,y)，并且第三种情况顶标值减少了 d，如此定会使等价子图扩大。就上例而言: 修改后 Lx(1)= 2, Lx(2)= 3, Lx(3)= 5, Ly(1)= 0, Ly(1)= 0, Ly(2)= 0, Ly(3)= 1。这时