KM 算法

上一篇博客讲了二分图匹配的匈牙利算法，但是匈牙利算法中的每个匹配边权重都是一样的，如果我们在匹配边权重不同的情况下得到最佳匹配，那么就需要用到KM算法。

基本原理

其实我们在理解了匈牙利算法之后，再来理解KM算法就简单了。

我们现在知道匈牙利算法能解决最大匹配的问题，现在加了权重，KM算法实际上就是想了个办法，将问题转换成了匈牙利算法可以解决的形式。

现在二分图带了权重，可以理解为加了一种约束，这种约束让我们优先选择那些权重大的边出来，进行匹配。

因此我们要先把权重最大的边都挑出来，学术一点，就是挑一个子图出来。因为我们挑出来的都是权重最大的边，我们只要在这个子图中，找到最大匹配，这个最大匹配一定是权重最大的（很重要，意思就是这个子图里，在上面随便找都是权重最大的匹配，这样我们就能用匈牙利算法解决问题了）。流程就是：

找权重最大的边组成的子图--------→在这个子图上找最大匹配

上述流程很简单吧，有一个问题是，我们都找最大权重的边组成子图，这个子图很小，很容易冲突。形象来说，大家找对象的要求都太高了，很可能会没法满足他们的要求。这时候只能委屈一部分人，让他稍微降低一下的要求，让他从别的人里挑对象。

这个KM算法的流程，核心思想就是：优先选择最满意的，因为要求太高找不到对象的那些人，降低标准扩大择偶范围，直到找到对象为止。

这个问题中，找最大匹配的那一部分我们会了呀，用匈牙利算法就搞定了。剩下就是两个问题了：

1. 怎么找到这个所谓的“权重最大的子图”。

2. 怎么扩大择偶范围。既不能降得太低，也不能不降。

上述两个问题，就是KM算法的精髓。

这个权重最大的子图，就是“相等子图”。扩大择偶范围，就是“顶标的更新—建立新的相等子图”的过程。

要注意的是，上面说的权重最大，并不是整个图的范围内权重越大越好，而是目前能力范围内我们能选的最大的权重边（毕竟有些人需要降低标准才能找到对象）。

第一个问题 如何寻找“权重最大的”子图？

首先强调一点，我们的这个子图的目的，是为了实现一个效果：

在这个子图上，不考虑权重找到最大匹配 等价于 在带权重的图上找权重最大的最大匹配。

我们挑一伙人出来，这些人彼此的满意度都比较高，那些低的暂时不考虑。在这伙人里找对象。找不到了再考虑加人进来。

为了实现这个目标，我们给每个人，增加一个顶标。我们暂不考虑这个顶标是怎么加的，将在下一步中再详细讲这个问题。现在假设我们已经有一个顶标了。

这个顶标是我们决定一条边是否加入子图的依据。顶标可以理解为择偶的最高标准，如果双方的适配程度达到了这个最高标准，就加入到择偶范围内来，就是加入到子图中。

因此，比如说小王择偶的最高标准是$S_{Wang}$ ，小李择偶最高标准$S_{li}$。小王和小李的喜欢程度是W（即二分图中，小王和小李的连线权重），若$W= S_{Wang} + S_{li}$就加入子图中，进入择偶候选人范围。注意到上面这个等式，于是这样选出来的子图，叫做相等子图。

然而这个最高标准，是不断变化的。也就是下一个问题，如何不断地调整最高标准，让择偶范围不断变化。

第二个问题 如何扩大择偶范围？

我们这里拿一个具体的例子来看。

这里有5个女生x1-x5， 5个男生y1-y5。他们之间为0就是没有连线，大于0的数是权重，就是他们相互喜欢的程度。

$$\begin{bmatrix} & 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 \end{bmatrix}$$

第一步，最高标准初始化。

需要注意的是，我们是一个无向的二分图，意思就是权重是双方共同的喜欢程度，因此可以选一个人作为代表就行了。于是，我们让女生做单方面的选择。

于是男生们的顶标都设为0。

一开始女生们都想找最喜欢的对象，我们将她们的最高标准都设为她们最喜欢的那个。比如，x1对所有男生都有意向，喜欢程度分别是3,5,5,4,1。那么她目前的最高标准就是5。

在第一次选择中，y2、y3加入择偶范围，其他三人暂不考虑。所有女生都这样，选出自己最喜欢的加入择偶范围。

我们就得到了子图

这样的好处就是，这样挑出来的子图中，彼此喜欢程度一定是最大的。这样我们就不用考虑权重的问题了，问题就变成了一个在局部子图上，挑选最大匹配的问题，就可以用匈牙利算法解决了。

走到这一步的时候，我们无法继续找到增广路径了，此时就要扩大择偶范围

第二步，最高标准调整。

我们随便选择一条上面没走下去的交替路（由于没有成功找到另一个未匹配的对象，所以这条交替路没有资格被称为增广路）比如就选这条：

x4----y2----x3----y3------x1----y2----???

这条路线，在很多文章里也会被成为交替树。一旦找到增广路，我们就能扩大匹配范围，给x4也找到对象。但是现在失败了，这个失败的本质是和路线上的人发生了冲突。2

于是我们看看，有哪些人和x4的失败有关。女生：x1，x3，x4。男生：y2，y3。

现在我们要协调这几个人的择偶最高标准（也就是他们的顶标），扩大择偶范围了。

首先，我们不能破坏原有的关系，原来的顶标都是设计好的，能保证选到自己最喜欢的对象。所以要保证他们之间最高标准不变，这样保证原来的匹配不会发生变化。

这里让上面和x4冲突的这些人里：女生的顶标减少，男生顶标增加，这样他俩合起来标准不变。

但是，女生的顶标减小了，其他人的机会就来了。

再回到刚刚我们挑子图的公式，就是小王配小李的这个等式，

现在小王因为和别人冲突了，降低了标准，W就减小了，也就是有些权重没那么大的边，现在有机会被加进子图里了。

现在女生：x1，x3，x4都喜欢y2和y3，发生冲突了，而y1,y4,y5还没被他们考虑。原本x1的标准是5，现在她要考虑y1的话，x1y1权重是3，需要降低2个标准。

同理，x1y4需要降低1； x3y1需要降低2， x3y4需要降低4-1=3；x3y5需要降低4-0=4。x4也一样算法。

所以考虑到最大权重，最少要降低1个标准。

因此我们把x1，x3，x4的标准-1，y2，y3对应+1。

在这个标准下，我们依旧要挑满足“两人顶标和=两人连线权重”的边。

可以看出来，x4同学降低标准后，所有男同学都满足她的标准了。

此时我们就可以给这个图找到完美匹配了,