[Note]KM最优匹配，匈牙利算法介绍

KM算法是用于求最优匹配的一种算法。

什么是最优匹配？

先说一下什么是“匹配”，既然是匹配，那肯定是有两方，且两方均可能有多个单一个体待匹配。

举个例子，假设有一家公司，它有很多个员工，也有很多个具体工作，让哪一个员工做哪一个工作，就是一个分配问题，也可以说是匹配问题。

再举个例子，假设有一个婚恋平台，有很多男生，有很多女生，为哪一个男生撮合哪一个女生，也是一个匹配问题。

然后说一下什么是“最优”，“最优”是一个目标，在公司的例子中，假设最优指的是公司效益最高，那么由于每个员工做哪一项工作，产生的效益是不一样的，所以给员工分配工作就不能随便分配，直观上，哪个员工做哪一项工作的效益越高，一般是优先分配的。

举个简单的例子：

假设有三个员工1、2、3，三项工作A、B、C。

员工1做每项工作所能产生的效益不一样，具体为做A工作效益为1，做B工作效益为0，做C工作效益为0。

将这些图写成一个矩阵：

第一行第一列就是员工1做A工作产生的效益，第一行第二列就是员工1做B工作的效益，以此类推。

要做最优匹配，明显就是做以下的分配即可，最大效益为3。

到此明确了目标，和一些基本概念，接下来看如何处理复杂的情况。

再举个例子，一个员工可能对每种工作都有所涉猎，且所产生的效益如下。

那么算法过程如下

首先要创建一个叫做顶标的东西，这个东西是用于辅助分配的。

顶标的意思其实就是顶点的标签，顶点就是任意员工或者任意工作，都属于顶点。

初始顶标，左边是每个员工的最大权重，右边都是0，这样设计的原因就是为了找到最优匹配，细节在后续说明。

给1号员工找工作

找路径的标准是，这条路径要满足“左右顶标和-权重==0”，这里只有1->C满足条件，具体数值是4+0-4=0，因此第一条路径就是1->C。至于为什么是这个条件，后续会说明。

由于C工作还未被分配，因此没有冲突。

然后看员工2

员工2找到的路径与员工1冲突，此时，会记录谁做工作C的收益更高，然后进行顶标更新，更新的目的是增加可选路径。

更新顶标的方法是，参与仲裁的对象，左边减法，右边加法，减去的数值和加的数值是一样的，称为slack，这里slack为1，1是怎么得到的呢？其实就是参与仲裁的任意一个员工，能够增加可选路径的最小数值。因为更新顶标就是为了增加路径，那么对应的计算也是为“增加路径”这一动作来服务。

更新了顶标，可以看到符合“左右顶标和-权重==0”这一条件的路径多了，然后根据谁的收益高，将对应路径分给收益更高的。

然后是员工3

员工3一开始都没有路径，因此同样更新顶标，增加可选路径。

更新后，员工3有了路径，但是发生了冲突，员工3占了员工1的工作，员工1退至求其次选择工作A，也会占掉员工2的工作，那么员工2没得选了，再次更新顶标，增加可选路径。

可以看到，更新顶标之后，员工1多了一条路径到工作B，然后再次仲裁，将收益高的路径优先保留，最终获得分配结果，最终收益为9.

顶标是什么含义，为什么需要顶标？

顶标在英文里是vertex label，就是顶点的标签的意思，什么是顶点，就是具体的员工和工作，也就是员工1、2、3和工作A、B、C，这6个都是顶点。标签就是打标签的意思。

这个顶标的作用，我认为主要与路径相关。

其一，顶标用于得到最优路径。

其二，冲突时，顶标的更新用于增加可选次优路径。

为什么以 “左右顶标和-权重==0“为标准，去画出路径？

先简单解释一下，什么是完美匹配。

假设有偶数个点需要两两匹配，所谓完美匹配，就是每个点都有独自的匹配对象，两两成对，没有遗漏，也没有多出来的点。

然后，以“左右顶标和-权重==0“这些路径，如果能找到的完美匹配，就是最优匹配。如果想了解细节，需要花时间看一下《图论》的推导。

我尝试简单解释一下，以这个匹配为例子

首先，明确我们的目标，是找到权重和最大的匹配。

由于顶标在初始化和更新时，遵循的条件是“左右顶标和≥权重”

比如，（员工1的顶标4+工作A/B/C的顶标0）≥他们之间路径的权重3/0/4。

所以，任意一种完美匹配，一定是：权重的总和≤顶标的总和。

比如1B，2A，3C，权重和=0+2+5=7，小于4+0+3+0+5+0=12

比如1C，2B，3A，权重和=4+1+0=5，同样小于12

看到这个条件，我们可以察觉到，怎么让权重和最大呢？上述这个不等式非常明显，权重总和最大时，就是等于左右顶标和的时候。

根据这个启发，我们找路径是怎么找的呢，就是以“左右顶标和＝权重”为条件去找路径的，如果最后能找到，最后找到的完美匹配，一定是：权重的总和=顶标的总和，因为权重和最大也就是等于左右顶标和，满足这个条件，就是权重和最大的完美匹配。

更新顶标的方式是让顶标减去一个值，这个理论是怎么来的？

参考

https://www.topcoder.com/thrive/articles/Assignment%20Problem%20and%20Hungarian%20Algorithm

Assignment Problem and Hungarian Algorithm 作者x-ray

《图论及其应用》 主编 张清华 清华大学出版社