KM(Kuhn-Munkres)算法求带权二分图的最佳匹配

1248 0 0

作者:小张人

KM(Kuhn-Munkres)算法求带权二分图的最佳匹配

算法流程

这里有一篇比较好的~~男女找对象指南~~博客讲解了KM算法的执行过程，生动而又形象。主要理解过程中是怎么满足配对条件的，不满足后怎么办，过程中降低期望值d是怎么求得的，在配对失败期望值进行更改以后发生了那些变化，这些变化为新的一轮的匹配带来了什么？

此处有链接

算法原理：

搞清楚算法流程后对算法的原理就会很好奇（可能吧~），为什么要这样做，这样做后为什么会产生这些改变，为什么利用这些改变就可以得出最终结果？

在详细介绍原理前，可以先看一下这篇博客（有图），根据算法流程介绍原理，可以直观感受一下，写的还是很清晰的，就是字有点小

此处有链接

算法的正确性基于以下定理：(相关概念就可以倒回去看了)

若由二分图中所有满足(lx(x)+ly(y)==weight(x,y))的边(x,y)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。

因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和（即不是最优匹配）。所以相等子图的完备匹配一定是二分图的最大权匹配。

初始时为了使(lx(x)+ly(y)>=weight(x,y))恒成立，令lx(x)为所有与顶点Xi关联的边的最大权，ly(y)=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。

我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点（因为没法跟Y匹配下去了，终止在X）。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d（注意是交错树中的顶点，也就是匹配的女生和被访问的男生），那么我们会发现：（这个过程就对应于男女生配对中女生配对失败后的情况）

1）两端都在交错树中的边(x,y)，lx(x)+ly(y)的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。

　　2）两端都不在交错树中的边(x,y)，lx(x),ly(y)都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。

　　3）X端不在交错树中，Y端在交错树中的边(x,y)，它的lx(x)+ly(y)的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。

　　4）X端在交错树中，Y端不在交错树中的边(x,y)，它的lx(x)+ly(y)的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。

现在的问题就是求d值了。为了使(lx(x)+ly(y)>=weight(x,y)) 始终成立，且至少有一条边进入相等子图，d应该等于：{(Minlx(x)+ly(y)-weight(x,y)|x在交错树中，y不在交错树中)}。

以上是KM算法的基本思想。但是朴素的实现方法，时间复杂度为O(n4)——需要找(O(n))次增广路，每次增广最多需要修改(O(n))次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为(O(n^2))。实际上KM算法的复杂度是可以做到(O(n^3))的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(x,y)时，如果它不在相等子图中，则让slack[y]变成原值与weight(x,y)-lx(x)-ly(y)的较小值（就是男生女生配对的求d的过程）。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d（对应就是未被访问的男生离女生更近了一步）。

代码

以下代码基于HDU2255奔小康赚大钱

#include <iostream>
#include <cstdio>
#include <memory.h>
#define max_n 305
#define INF 0x3f3f3f3f
using namespace std;
int n;//一个集合中的顶点数
int love[max_n][max_n];//两个不同集合点之间的权值，即男女好感度
int ex_girl[max_n];//女生顶标
int ex_boy[max_n];//男生顶标
int vis_girl[max_n];//记录女生是否参与匹配
int vis_boy[max_n];//记录男生是否被尝试匹配
int slack[max_n];//松弛函数，以求出顶标的最小改变量d
int match[max_n];//记录匹配关系

int dfs(int girl)
{
    vis_girl[girl] = 1;
    for(int boy = 0;boy<n;boy++)
    {
        if(vis_boy[boy]) continue;//每次dfs每个男生都只能被访问一次
        int gap = ex_girl[girl]+ex_boy[boy]-love[girl][boy];//看看L(x)+L(y)-weight(x,y)的值
        if(gap==0)//如果满足匹配规则
        {
            vis_boy[boy] = 1;//当前男生已被访问
            if(match[boy]==-1||dfs(match[boy]))//如果男生无主或者他的女生可以抛弃他
            {
                match[boy] = girl;//就给男生匹配新的女生
                return 1;//配对成功
            }
        }
        else
        {
            slack[boy] = min(gap,slack[boy]);//如果无法满足匹配规则，看男生要能跟女生匹配还差多少，不断更新这个差值
        }
    }
    return 0;
}
int KM()
{
    memset(match,-1,sizeof(match));//全部标记为未匹配
    memset(ex_boy,0,sizeof(ex_boy));//男生顶标初始化为零
    for(int i = 0;i<n;i++)//求出女生顶标，即这个女生与男生好感度的最大值
    {
        ex_girl[i] = love[i][0];
        for(int j = 1;j<n;j++)
        {
            ex_girl[i] = max(ex_girl[i],love[i][j]);
        }
    }
    for(int i = 0;i<n;i++)//对每个女生开始匹配
    {
        fill(slack,slack+n,INF);//松弛函数初始化为无限大
        while(1)
        {
            memset(vis_girl,0,sizeof(vis_girl));//每次dfs前清除标记数组
            memset(vis_boy,0,sizeof(vis_boy));
            if(dfs(i)) break;//当前女生匹配成功
            int d = INF;//若未成功
            for(int j = 0;j<n;j++)
            {
                if(vis_boy[j]==0)
                {
                    d = min(d,slack[j]);//看最小需要将第多少期望值能够匹配成功
                }
            }
            for(int j = 0;j<n;j++)
            {
                if(vis_girl[j])
                {
                    ex_girl[j] -= d;//对参与匹配的女生降低期望值
                }
                if(vis_boy[j])
                {
                    ex_boy[j] += d;//对被访问的男生提高期望值，上面两个步骤使得
                    //1.参与匹配的女生跟满足匹配规则匹配的男生仍然可匹配
                    //2.参与匹配的女生跟本未被访问的男生可能满足规则，扩大了匹配范围
                    //3.未参与匹配的女生跟更不可能匹配被访问的男生
                    //4.未参与匹配的女生跟未被访问的男生依然不能匹配
                }
                else
                {
                    slack[j] -= d;//未被访问的男生离女生跟进了一步
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i<n;i++)
    {
        if(match[i]>-1)
        {
            ans += love[match[i]][i];
        }
    }
    return ans;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i = 0; i<n; i++)
        {
            for(int j = 0; j<n; j++)
            {
                scanf("%d",&love[i][j]);
            }
        }
        printf("%dn",KM());
    }
    return 0;
}

参考文章

x_y_q_ ，带权二分图的最佳匹配（KM算法）， https://blog.csdn.net/x_y_q_/article/details/51927054 （偏向原理）

SixDayCoder，二分图的最佳完美匹配——KM算法，https://blog.csdn.net/sixdaycoder/article/details/47720471 （概念向）

wenr，KM算法详解+模板，https://www.cnblogs.com/wenruo/p/5264235.html （算法流程介绍）

kuangbin， Kuhn-Munkres算法（二分图最大权匹配），https://www.cnblogs.com/kuangbin/archive/2012/08/19/2646535.html （总结向）

内容来源于网络如有侵权请私信删除

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

KM(Kuhn-Munkres)算法求带权二分图的最佳匹配