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