二分图最优匹配（转）

转自这个牛

二分图最优匹配：对于二分图的每条边都有一个权（非负），要求一种完备匹配方案，使得所有匹配边的权和最大，记做最优完备匹配。（特殊的，当所有边的权为1时，就是最大完备匹配问题） 解二分图最优匹配问题可用穷举的方法，但穷举的效率=n！，所以我们需要更加优秀的算法。 先说一个定理：设M是一个带权完全二分图G的一个完备匹配，给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示，第j个y顶点的可行标用ly[j]表示)，如果对所有的边(i,j) in G,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权)，且对所有的边(i,j) in M,都有lx[i]+ly[j]=w[i,j]成立，则M是图G的一个最优匹配。 Kuhn－Munkras算法（即KM算法）流程： v      (1)初始化可行顶标的值 v      (2)用匈牙利算法寻找完备匹配 v      (3)若未找到完备匹配则修改可行顶标的值 v      (4)重复(2)(3)直到找到相等子图的完备匹配为止 KM算法主要就是控制怎样修改可行顶标的策略使得最终可以达到一个完美匹配，首先任意设置可行顶标（如每个X节点的可行顶标设为它出发的所有弧的最大权，Y节点的可行顶标设为0），然后在相等子图中寻找增广路，找到增广路就沿着增广路增广。而如果没有找到增广路呢，那么就考虑所有现在在匈牙利树中的X节点（记为S集合），所有现在在匈牙利树中的Y节点（记为T集合），考察所有一段在S集合，一段在not T集合中的弧，取       delta = min {l(xi)+l(yj)-w(xi,yj) , | xi in S, yj  in not T}   。明显的，当我们把所有S集合中的l(xi)减少delta之后，一定会有至少一条属于(S, not T)的边进入相等子图，进而可以继续扩展匈牙利树，为了保证原来属于(S,T )的边不退出相等子图，把所有在T集合中的点的可行顶标增加delta。随后匈牙利树继续扩展，如果新加入匈牙利树的Y节点是未盖点，那么找到增广路，否则把该节点的对应的X匹配点加入匈牙利树继续尝试增广。 复杂度分析：由于在不扩大匹配的情况下每次匈牙利树做如上调整之后至少增加一个元素，因此最多执行n次就可以找到一条增广路，最多需要找n条增广路，故最多执行n^2次修改顶标的操作，而每次修改顶标需要扫描所有弧，这样修改顶标的复杂度就是O(n^2)的，总的复杂度是O(n^4)的。     对于not T的每个元素yj，定义松弛变量slack(yj) =min{l(xi)+l(yj)-w(xi,yj), | xi in S}，很明显每次的delta = min{slack(yj), | yj  in not T}，每次增广之后用O(n^2)的时间计算所有点的初始slack，由于生长匈牙利树的时候每条弧的顶标增量相同，因此修改每个slack需要常数时间（注意在修改顶标后和把已盖Y节点对应的X节点加入匈牙利树的时候是需要修改slack的）。这样修改所有slack值时间是O(n)的，每次增广后最多修改n次顶标，那么修改顶标的总时间降为O(n^2)，n次增广的总时间复杂度降为O(n^3)。事实上这样实现之后对于大部分的数据可以比O(n^4)的算法快一倍左右。 利用二分图匹配的匈牙利算法和KM算法，我们可以求解大部分的关于二分图的问题，它们提供了求解最大匹配和最优匹配的有效算法，在具体编程时我们只要多注意优化，我们就可以得出求解这类问题的有效方法，从而可以对这类实际问题进行有效合理的解决

下面的转自这个牛

带权二分图的最优匹配 Kuhn-Munkres算法

问题背景：

分工问题如下：某公司有工作人员x1,x2,...,xn,他们去做工作y1,y2,...,yn,每人适合做其中的一项或几项工作，每个人做不同的工作的效益不一样，我们需要制定一个分工方案，使公司的总效益最大，这就是所谓最佳分配问题， 它们数学模型如下：

数学模型：
    G是加权完全二分图，V(G)的二分图划分为X，Y；X={x1,...,xn},Y={y1,y2,...yn},w(xiyi)>=0是工作人员xi做yi工作时的效益，求权最大的完备匹配，这种完备匹配称为最佳匹配。
这个问题好象比较的棘手，用穷举法的话举也举死了，效率很低。本节给出一种有效算法，为此，先引入一个定义和一个定理。

定义1   映射l:V(G)->R，满足：任意x∈X,任意y∈Y,成立
l(x)+l(y)>=w(xy),
则称l(v)是二分图G的可行顶标；令
El={xy|xy∈E(G),l(x)+l(y)=w(xy)},
称以El为边集的G之生成子图为相等子图，记为Gl
可行顶标是存在的，例如
l(x)=max w(xy),x∈X;
l(y)=0, y∈Y.

定理1 Gl的完备匹配即为G的最佳匹配。
证：设M*是Gl的一个完备匹配，因Gl是G的生成子图，故M*也是G的完备匹配。M*中的边之端点集合含G的每个顶点恰一次，所以
W(M*)=Σw(e)=Σl(v) (e∈M*,v∈V(G)).
另一方面，若M是G中任意一个完备匹配，则
W(M)=Σw(e)<=Σl(v) (e∈M,v∈V(G)),
所以
W(M*)>=W(M)，
即M*是最佳匹配，证毕。

定理1告知，欲求二分图的最佳匹配，只需用匈牙利算法求取其相等子图的完备匹配；问题是，当Gl中无完备匹配时怎么办？Kuhn和Munkras给出修改顶标的一个算法，使新的相等子图的最大匹配逐渐扩大，最后出现相等子图的完备匹配。

Kuhn-Munkras算法：
(0) 选定初始的可行顶标l,确定Gl,在Gl中选取一个匹配M。
(1) X中顶皆被M许配，止，M即为最佳匹配；否则，取Gl中未被M许配的顶u,令S={u},T为空。
(2) 若N(S)真包含T，转(3)；若N(S)=T，取
al=min(l(x)+l(y)-w(xy)}(x∈S,y∈T),
l(v)-al,v∈S;
l(v)= l(v)+al,v∈T;
l(v),其它。
l=l,Gl=Gl。
(3) 选N(S)-T中一顶y,若y已被M许配，且yz∈M,则S=S∪{z},T=T∪{y},转(2)；否则，取Gl中一个M的可增广轨P(u,y),令M=M⊙E(P)，转(1)。

上面的算法看得有点莫名，改那个可行顶标怎么改改就好了？还是得看盾例子
例1   已知K5,5的权矩阵为
y1 y2 y3 y4 y5
x1 3 5 5 4 1
x2 2 2 0 2 2
x3 2 4 4 1 0
x4 0 1 1 0 0
x5 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)=max(3,5,5,4,1}=5,l(x2)=max{2,2,0,2,2}=2,l(x3)=max(2,4,4,1,0}=4,l(x4)=max{0,1,1,0,0}=1,l(x5)=max{1,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. (x∈S,y∈T)
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。

我们看出：al>0；修改后的顶标仍是可行顶标；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)。再用匈牙利算法求出最大匹配，再把匹配中的每一边的权值加起来就是最后的结果了。

KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[i]，顶点Yi的顶标为B[i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终成立。KM算法的正确性基于以下定理：
若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。
这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。
初始时为了使A[i]+B[j]>=w[i,j]恒成立，令A[i]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。
我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：
两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。
两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。
X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。
X端在交错树中，Y端不在交错树中的边(i,j)，它的A[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。
　　现在的问题就是求d值了。为了使A[i]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于min{A[i]+B[j]-w[i,j]|Xi在交错树中，Yi不在交错树中}。
　　以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3) 的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的slack值都减去d。