算法笔记：KM算法（Kuhn-Munkres Algorithm）-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法笔记：KM算法（Kuhn-Munkres Algorithm）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

带权二分图的最优匹配问题

算法笔记：匈牙利算法_UQI-LIUWJ的博客-CSDN博客

1 KM算法举例

二部图的每条关系之间加入了权重

算法笔记：KM算法（Kuhn-Munkres Algorithm）

首先对每个顶点赋值，称为顶标，将左边的顶点赋值为与其相连的边的最大权重，右边的顶点赋值为0。
然后开始匹配
- 匹配的原则是：
  - 只和权重与左边分数（顶标）相同（或比顶标大）的边进行匹配（边权重=左+右）
  - 若找不到边匹配，对此条路径的所有左边顶点的顶标减d，所有右边顶点的顶标加d。参数d我们在这里取值为0.1。
对于左1，与顶标分值相同的边先标蓝。
然后是左2，与顶标分值相同的边标蓝
然后是左3，发现与右1已经与左1配对。
- 首先想到让左3更换匹配对象
  - 然而根据匹配原则，只有权值大于等于0.9+0=0.9（左顶标加右顶标）的边能满足要求。于是左3无法换边。
- 那左1能不能换边呢？
  - 对于左1来说，只有权值大于等于0.8+0=0.8的边能满足要求，无法换边。
  - 此时根据KM算法，应对所有冲突的边的顶点做加减操作，令左边顶点值减0.1，右边顶点值加0.1。
  - 再进行匹配操作，发现左3多了一条可匹配的边，因为此时左3对右2的匹配要求只需权重大于等于0.8+0即可，所以左3与右2匹配！
最后进行左4的匹配，由于左4唯一的匹配对象右3已被左2匹配，发生冲突。进行一轮加减d操作，再匹配，左四还是匹配失败。两轮以后左4期望值降为0，放弃匹配左4。