加权二分图的最优匹配问题（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||
| X5' | 0 | 0 | 0 | 0 | 0 |
|---|
||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||
| X5’ | 7 | 7 | 7 | 7 | 7 |
|---|
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 算法的原理需要一些可视化的方式会更好，这里暂时不详细讲解了，有兴趣可以参考下面这个例子讲解
最后我们还有待求证的是在数学建模中如何阐述一个算法的原理，篇幅以及阐述方式是怎么样的 🥹
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于