从匈牙利到KM

1、前言

学习是一个痛苦的过程，让我们养成了不求甚解的习惯。

2、匈牙利算法

嗯，首先网上已经有很多啦。但是我觉得很多还是抠不清楚细节，于是就有了这篇文章。 匹配就是一种两两不相接的边的集合，二分匹配就是二分图的匹配，匈牙利的基础可以随便看一篇。

bool find(int x){
    int i,j;
    for (j=1;j<=m;j++){    //扫描每个妹子
        if (line[x][j]==true && used[j]==false)      
        //如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题，但是没有成功，所以就不用瞎费工夫了）
        {
            used[j]=1;
            if (girl[j]==0 || find(girl[j])) { 
                //名花无主或者能腾出个位置来，这里使用递归
                girl[j]=x;
                return true;
            }
        }
    }
    return false;
}
int match ()
{
      int all = 0;
      for (i=1;i<=n;i++)
      {
          memset(used,0,sizeof(used));    //这个在每一步中清空
          if find(i) all+=1;
      }
      return all;
}

以上代码是我从一篇的链接中拿过来的，line数组存的是二分图<X,Y>的边权，不难证明从X中一个点x出发若匹配的数量增加，等价于存在一条从x出发的增广路。算法的思想就是对X中每个点通过find来深搜增广路。由于每次只会递归used为0的点。所以递归深度为O(n)，find的复杂度是O(n^{2)，整个算法的复杂度是O(n}3)。

嗯，到这里没什么问题，一般的blog讨论到这里也结束了。但是当你仔细看find，会发现这个函数好像跟我们平时的搜索不太一样。

bool find(int x){
    int i,j;
    for (j=1;j<=m;j++){ 
        if (line[x][j]==true && used[j]==false)  
        {
            used[j]=1;
            if (girl[j]==0 || find(girl[j])) { 
                girl[j]=x;
                return true;
            }
            //used[j]=0;  平时这里要将赋值过得used还原。
        }
    }
    return false;
}

平时搜索失败的时候是需要把上下文还原的，也就是去掉注释。然而一旦去掉注释，这将是一个指数复杂度的搜索算法。于是我们有理由相信，不需要还原used恰恰是匈牙利算法对搜索的一种优化，而为什么可以这样优化，这种正确性则是我们需要证明的事，也是该算法的精髓。

我们考虑一个去掉上述注释的find函数，此时就是普通的搜索，这样算法肯定是对的，接下来我们要证明这样搜索的结果与注释时是一样的。

我们要解决的问题是<X,Y>的二分图中，已经used的部分组成的集合称作前缀。初始时前缀为空集。从X中一个点x0出发在图中找增广路径，查找所有边，若对应的y之前未匹配则直接返回找到解。否则将y加入前缀，并从y之前匹配的点开始继续搜索，搜索成功则直接返回答案，否则将该点剔除前缀。

不难发现以下结论。

1. 在搜索过程中，除了找到增广路结束搜索。否则每个匹配的Y中的点都对应同一个X中的点。
2. 若从一个前缀为S时从x出发搜索失败，则前缀为S超集时从x出发也搜索失败。

以上发现比较显然，就不证明啦。

定理1 若从一个前缀为S时搜索到y时继续搜索失败，则前缀为S超集时搜索到y继续搜索也失败。
证明：由搜索失败知y肯定有匹配的点。由结论1知道在搜索成功前y匹配的点始终不会变化。再根据结论2可证明。

定义1 在前缀S时从x出发搜索和前缀T时从x出发搜索时都有解或者都无解，则称S和T在x处前缀等价。

定理2 前缀S和前缀T在x处等价，前缀T和前缀P在x处等价，则前缀S和前缀P在x处等价。
证明：由 定义1知，显然。

定理3 前缀S和前缀T在x处等价，若P是前缀S的超集，T是P的超集。则前缀S和前缀P在x处等价，前缀T和前缀P在x处等价。
证明：
前缀S与前缀T在x处等价，知前缀S和前缀T在x处搜索都有解或者都无解。
若前缀T和前缀S在x处有解，则由结论2的逆否命题及前缀T在x处有解知前缀P在x处有解。
若前缀T和前缀S在x处无解，则由结论2及前缀S在x处无解知前缀P在x处无解。
综上所述，则前缀S和前缀P在x处等价，前缀T和前缀P在x处等价。

定理4 在前缀集合S时从y的匹配搜索时，设所有前缀S从y的匹配出发访问过的搜索失败的点为Q，则S和S并Q在y的匹配处前缀等价。
证明：由于还在搜索，所以目前的匹配都是失败的。设从前缀S开始从y的匹配访问过的点Q中，设至少一次在第k次递归中出现时的点的集合为C(k)。
Q = C(0) 并 C(1) 并 C(2) ...

下面用数学归纳法证明S和S并C(0)并C(1)...并C(n)在y处前缀等价。
对于C(0)中任意一个点y0，由于S并{y0}在y0处无解，则S并{y0}的超集在y0处也无解。所以y0出现在之后搜索的任何位置，从那里搜索必然无解。这相当于C(0)中任意一个点在之后被搜索到都将得不到解，则S并C(0)和S在y处前缀等价。
设n=k时，S和S并C(0)并C(1)...并C(k)在y处等价。
n=k+1是，设D=S并C(0)并C(1)...并C(k)。以前缀D从y的匹配开始搜索。由于C(k+1)中的点都可以从C(k)中走过来且都失败了，因此若是从其他地方搜索到C(k+1)必然是D的超集由结论2也会失败。故前缀D和D并C(k+1)在y匹配处前缀等价，又S和D在y匹配处前缀等价。由定理2知S和D并C(k+1)在y匹配处前缀等价，即S和S并C(0)并C(1)...并C(k)并C(k+1)在y匹配处前缀等价。

由于搜索是有限的，我们知道存在m使得k>m时C(k)为空集。
Q = C(0) 并 C(1) 并 C(2) ... 并C(m)。
S并C(0)并C(1)...并C(m)和S在y处等价，有S并Q和S在y处前缀等价。

定理5 在前缀集合S时从y的匹配搜索时，设所有由深搜访问过的搜索失败的点的集合为Q，则S和S并Q在y的匹配处前缀等价。
证明：显然，任何一个访问过的点，一定是由到y的过程中某个阶段失败的。由定理4，可以把当时的前缀替换为前缀并上该前缀起搜索失败点的集合。这些所有阶段的并集是Q。则到y时前缀可以替换为S并Q。得证。

由定理5知可以把之前访问过的点并入前缀，即used。所以加不加注释，搜索出来的结果是一样的。

3、KM算法

KM算法的话，就是二分图的匹配带权，特别注意不是求数量最多的匹配，而是求匹配中权和最大的匹配。网上很多O(n^4)实现。这里有一个比较好的O(n^3)实现。

KM算法的图使用邻接矩阵来表示，没有边的点之间加一个权值为0的边。这样可以保证无论怎么连都存在完美匹配。然后通过给二分图的两边的点顶标，维护每条边的权值都小于两边的顶标和，对于一个完备匹配，若每条边的权值等于两个点的顶标和，则一定是最大权匹配。因为该权和等于所有顶标和，若存在更大的权匹配，则与每条边的权值都小于两边的顶标和矛盾。算法的具体细节在链接里已经讲得比较清楚啦。

下面讲一些KM的讨论，若边有负权，算法仍然成立。情况与加好零边后给所有的边加上最小负数的绝对值再跑算法一直。因为一定有完美匹配，多出来的值是固定的。
若二分图两边点的个数不相等，这样匹配就不能覆盖所有顶标，二分图的正确性不能保证，因此KM算法只能解决二分图两边点数相等的情况。