KM算法详解
参考:https://www.cnblogs.com/logosG/p/logos.htmlhttp://www.mamicode.com/info-detail-2527621.htmlhttps://blog.csdn.net/songbai1997/article/details/82014828KM算法(Kuhn-Munkres),用来求带权二分图的最大权匹配(最优匹配)。一、KM算法详解
参考:
- KM算法(Kuhn-Munkres),用来求带权二分图的最大权匹配(最优匹配)。
一、KM算法详解
1. 问题思考
-
示例:如果一个公司里每个员工做每件工作的效率各不相同,我们如何得到一个最优匹配使得整个公司的工作效率最大呢?
这种问题被称为带权二分图的最优匹配问题,可由KM算法解决。比如上图,A做工作a的效率为3,做工作c的效率为4…以此类推。
不了解KM算法的人如何解决这个问题?我们只需要用匈牙利算法找到所有的最大匹配,比较每个最大匹配的权重,再选出最大权重的最优匹配即可。这不失为一个解决方案,但是,如果公司员工的数量越来越多,此种算法的实行难度也就越来越大,我们必须另辟蹊径:KM算法。
2. 算法步骤
KM算法解决此题的步骤如下所示:
-
首先对每个顶点赋值,将左边的顶点赋值为最大权重,右边的顶点赋值为0。
如图,我们将顶点A赋值为其两边中较大的4。
-
进行匹配,我们匹配的原则是:只与权重相同的边匹配,若是找不到边匹配,对此条路径的所有左边顶点-1,右边顶点+1,再进行匹配,若还是匹配不到,重复+1和-1操作。(这里看不懂可以跳过,直接看下面的操作,之后再回头来看这里。)
对A进行匹配,符合匹配条件的边只有Ac边。
匹配成功!
-
接下来我们对B进行匹配,顶点B值为3,Bc边权重为3,匹配成~ 等等,A已经匹配c了,发生了冲突,怎么办?我们这时候第一时间应该想到的是,让B换个工作,但根据匹配原则,只有Bc边 3+0=3 满足要求,于是B不能换边了,那A能不能换边呢?对A来说,也是只有Ac边满足4+0=4的要求,于是A也不能换边,走投无路了,怎么办?
-
从常识的角度思考:其实我们寻找最优匹配的过程,也就是帮每个员工找到他们工作效率最高的工作,但是,有些工作会冲突,比如现在,B员工和A员工工作c的效率都是最高,这时我们应该让A或者B换一份工作,但是这时候换工作的话我们只能换到降低总体效率值的工作,也就是说,如果令R=左边顶点所有值相加,若发生了冲突,则最终工作效率一定小于R,但是,我们现在只要求最优匹配,所以,如果A换一份工作降低的工作效率比较少的话,我们是能接受的(对B同样如此)。
在KM算法中如何体现呢?
现在参与到这个冲突的顶点是A,B和c,令所有左边顶点值-1,右边顶点值+1,即 A-1,B-1,c+1,结果如下图所示。
-
我们进行了上述操作后会发现,若是左边有n个顶点参与运算,则右边就有n-1个顶点参与运算,整体效率值下降了1*(n-(n-1))=1 ,而对于A来说,Ac本来为可匹配的边,现在仍为可匹配边(3+1=4),对于B来说,Bc本来为可匹配的边,现在仍为可匹配的边(2+1=3),我们通过上述操作,为A增加了一条可匹配的边Aa,为B增加了一条可匹配的边Ba。
现在我们再来匹配,对B来说,Ba边 2+0=2,满足条件,所以B换边,a现在为未匹配状态,Ba匹配!
-
我们现在匹配最后一条边C,Cc:5+1!=5,C边无边能匹配,所以C-1。
-
现在Cc边 4+1=5,可以匹配,但是c已匹配了,发生冲突,C此时不能换边,于是便去找A,对于A来说,Aa此时也为可匹配边,但是a已匹配,A又去找B。
-
B现在无边可以匹配了,2+0!=1 ,现在的路径是C→c→A→a→B,所以A-1,B-1,C-1,a+1,c+1。如下图所示。
-
对于B来说,现在Bb:1+0=1 可匹配!
-
使用匈牙利算法,对此条路径上的边取反(匈牙利路径是Cc-cA-Aa-aB-Bb,其中aB和cA是已经匹配的,取反就剩下了,Cc/Aa/Bb 三组匹配,至此,两组匹配变成三组匹配,算法完成)。
如图,便完成了此题的最优匹配。读者可以发现,这题中冲突一共发生了3次,所以我们一共降低了3次效率值,但是我们每次降低的效率值都是最少的,所以我们完成的仍然是最优匹配!
- 这就是KM算法的整个过程,整体思路就是:每次都帮一个顶点匹配最大权重边,利用匈牙利算法完成最大匹配,最终我们完成的就是最优匹配!
二、KM算法实现:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 300 + 10;
const int INF = 0x3f3f3f3f;
int wx[maxn], wy[maxn];//每个点的顶标值(需要根据二分图处理出来)
int cx[maxn], cy[maxn];//每个点所匹配的点
int visx[maxn], visy[maxn];//每个点是否加入增广路
int cntx, cnty;//分别是X和Y的点数
int Map[maxn][maxn];//二分图边的权值
int slack[maxn];//边权和顶标最小的差值
bool dfs(int u)//进入DFS的都是X部的点
{
visx[u] = 1;//标记进入增广路
for(int v = 1; v <= cnty; v++)
{
if(!visy[v] && Map[u][v] != INF)//如果Y部的点还没进入增广路,并且存在路径
{
int t = wx[u] + wy[v] - Map[u][v];
if(t == 0)//t为0说明是相等子图
{
visy[v] = 1;//加入增广路
//如果Y部的点还未进行匹配
//或者已经进行了匹配,可以从原来的匹配反向找到增广路
//那就可以进行匹配
if(cy[v] == -1 || dfs(cy[v]))
{
cx[u] = v;
cy[v] = u;//进行匹配
return 1;
}
}
else if(t > 0)//此处t一定是大于0,因为顶标之和一定>=边权
{
slack[v] = min(slack[v], t);
//slack[v]存的是Y部的点需要变成相等子图顶标值最小增加多少
}
}
}
return false;
}
int KM()
{
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
memset(wx, 0, sizeof(wx));//wx的顶标为该点连接的边的最大权值
memset(wy, 0, sizeof(wy));//wy的顶标为0
for(int i = 1; i <= cntx; i++)//预处理出顶标值
{
for(int j = 1; j <= cnty; j++)
{
if(Map[i][j] == INF)continue;
wx[i] = max(wx[i], Map[i][j]);
}
}
for(int i = 1; i <= cntx; i++)//枚举X部的点
{
memset(slack, INF, sizeof(slack));
while(1)
{
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if(dfs(i))break;//已经匹配正确
int minz = INF;
for(int j = 1; j <= cnty; j++)
if(!visy[j] && minz > slack[j])
//找出还没经过的点中,需要变成相等子图的最小额外增加的顶标值
minz = slack[j];
//和全局变量不同的是,全局变量在每次while循环中都需要赋值成INF,每次求出的是所有点的最小值
//而slack数组在每个while外面就初始化好,每次while循环slack数组的每个值都在用到
//在一次增广路中求出的slack值会更准确,循环次数比全局变量更少
//还未匹配,将X部的顶标减去minz,Y部的顶标加上minz
for(int j = 1; j <= cntx; j++)
if(visx[j])wx[j] -= minz;
for(int j = 1; j <= cnty; j++)
//修改顶标后,要把所有不在交错树中的Y顶点的slack值都减去minz
if(visy[j])wy[j] += minz;
else slack[j] -= minz;
}
}
int ans = 0;//二分图最优匹配权值
for(int i = 1; i <= cntx; i++)
if(cx[i] != -1)ans += Map[i][cx[i]];
return ans;
}
int n, k;
int main()
{
while(scanf("%d", &n) != EOF)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
scanf("%d", &Map[i][j]);
}
cntx = cnty = n;
printf("%d\n", KM());
}
return 0;
}
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)