KM算法是用于求最优匹配的一种算法。什么是最优匹配先说一下什么是“匹配”既然是匹配那肯定是有两方且两方均可能有多个单一个体待匹配。举个例子假设有一家公司它有很多个员工也有很多个具体工作让哪一个员工做哪一个工作就是一个分配问题也可以说是匹配问题。再举个例子假设有一个婚恋平台有很多男生有很多女生为哪一个男生撮合哪一个女生也是一个匹配问题。然后说一下什么是“最优”“最优”是一个目标在公司的例子中假设最优指的是公司效益最高那么由于每个员工做哪一项工作产生的效益是不一样的所以给员工分配工作就不能随便分配直观上哪个员工做哪一项工作的效益越高一般是优先分配的。举个简单的例子假设有三个员工1、2、3三项工作A、B、C。员工1做每项工作所能产生的效益不一样具体为做A工作效益为1做B工作效益为0做C工作效益为0。将这些图写成一个矩阵第一行第一列就是员工1做A工作产生的效益第一行第二列就是员工1做B工作的效益以此类推。要做最优匹配明显就是做以下的分配即可最大效益为3。到此明确了目标和一些基本概念接下来看如何处理复杂的情况。再举个例子一个员工可能对每种工作都有所涉猎且所产生的效益如下。那么算法过程如下首先要创建一个叫做顶标的东西这个东西是用于辅助分配的。顶标的意思其实就是顶点的标签顶点就是任意员工或者任意工作都属于顶点。初始顶标左边是每个员工的最大权重右边都是0这样设计的原因就是为了找到最优匹配细节在后续说明。给1号员工找工作找路径的标准是这条路径要满足“左右顶标和-权重0”这里只有1-C满足条件具体数值是40-40因此第一条路径就是1-C。至于为什么是这个条件后续会说明。由于C工作还未被分配因此没有冲突。然后看员工2员工2找到的路径与员工1冲突此时会记录谁做工作C的收益更高然后进行顶标更新更新的目的是增加可选路径。更新顶标的方法是参与仲裁的对象左边减法右边加法减去的数值和加的数值是一样的称为slack这里slack为11是怎么得到的呢其实就是参与仲裁的任意一个员工能够增加可选路径的最小数值。因为更新顶标就是为了增加路径那么对应的计算也是为“增加路径”这一动作来服务。更新了顶标可以看到符合“左右顶标和-权重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。所以任意一种完美匹配一定是权重的总和≤顶标的总和。比如1B2A3C权重和0257小于40305012比如1C2B3A权重和4105同样小于12看到这个条件我们可以察觉到怎么让权重和最大呢上述这个不等式非常明显权重总和最大时就是等于左右顶标和的时候。根据这个启发我们找路径是怎么找的呢就是以“左右顶标和权重”为条件去找路径的如果最后能找到最后找到的完美匹配一定是权重的总和顶标的总和因为权重和最大也就是等于左右顶标和满足这个条件就是权重和最大的完美匹配。更新顶标的方式是让顶标减去一个值这个理论是怎么来的参考https://www.topcoder.com/thrive/articles/Assignment%20Problem%20and%20Hungarian%20AlgorithmAssignment Problem and Hungarian Algorithm 作者x-ray《图论及其应用》 主编 张清华 清华大学出版社