KM 算法

加权二分图的最优匹配问题（Kuhn-Munkres Algorithm）

前面的二分图最大匹配可以视为权重全为 1 的特殊情形

温馨提示：这个模型可以抽象为整数规划问题，KM 算法的原理与数学证明实在是很繁琐，我自己研究了很多遍还是不太明白，数学证明需要结合图论和线性代数，比较困难 😭

一、加权二分图的最优匹配模型

最优匹配：

是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和​最大

成本矩阵的构建

我写了一个例子，下面是一个有权无向二分图，下面我介绍最佳匹配模型的成本矩阵的构建

​​

||Y1|Y2|Y3|Y4|Y5|（1）这个表格的含义是对左边图的转化，现在我们需要选出最佳匹配，也就是每行最多选一个，每列最多选一个，使得选出来的数总和最大 |
|X1|1|4||3|||
|X2|5|
|2||7||
|X3|4|1|3|5|6||
|X4|||||5||

||Y1|Y2|Y3|Y4|Y5|（2）但是实际上成本矩阵需要完整的方阵，所以我们给矩阵补全，没有连接的我们记为 0，以及加上一个 X5‘，最后得到匹配结果后删去这些位置即可 |
|X1|1|4|0|3|0||
|X2|5|0|2|0|7||
|X3|4|1|3|5|6||
|X4|0|0|0|0|5||

||Y1|Y2|Y3|Y4|Y5|（3）实际上 linear_assignment()这个函数包是计算匹配使得匹配边上的权值和​最小的，所以这个问题我们需要把最大化转化为最小化，我们设置一个很大的数字（大于目前矩阵的所有数字，然后用它减去目前的数字），这里我们取 7|
|X1|6|3|7|4|7||
|X2|2|7|5|7|0||
|X3|3|6|4|2|1||
|X4|7|7|7|7|2||

	Y1	Y2	Y3	Y4	Y5
X1	6	3	7	4	7
X2	2	7	5	7	0
X3	3	6	4	2	1
X4	7	7	7	7	2
X5’	7	7	7	7	7

最后我们得到了成本矩阵，我们需要每一行找且仅找一个数，每一列只找且仅找一个数

将这个问题一般化也就是如下的整数数学规划模型（指派模型） ：

二、KM 算法(有的也叫匈牙利算法）

实际使用中直接通过矩阵调用 sklearn 中的函数****linear_assignment()

• KM 算法的本质依旧是寻找增广路径，但是考虑到加权就更加复杂
• 从成本矩阵来考虑，其实每一步操作等价于对成本矩阵进行初等变换（保证成本矩阵的秩不变-信息熵)
• 能力有限，阐述清楚 KM 算法的原理需要一些可视化的方式会更好，这里暂时不详细讲解了，有兴趣可以参考下面这个例子讲解

KM 算法详解-CSDN 博客

最后我们还有待求证的是在数学建模中如何阐述一个算法的原理，篇幅以及阐述方式是怎么样的 🥹

‍