图论中有提及相关问题。其中最经典问题之一男女匹配问题。
问:如何尽可能多的让男女都可以匹配上?
解释:线段表示双方可以匹配
匈牙利算法解决的问题概述:有 n 项不同的任务,需要 n 个工人分别完成其中的 1 项,每个人完成任务的成本不一样。如何分配任务使得花费成本最少?
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人甲 | 1 | 3 | 2 |
工人乙 | 3 | 6 | 5 |
工人丙 | 2 | 8 | 4 |
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人甲 | 0 | 2 | 1 |
工人乙 | 0 | 3 | 2 |
工人丙 | 0 | 6 | 2 |
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人甲 | 0 | 0 | 0 |
工人乙 | 0 | 1 | 1 |
工人丙 | 0 | 4 | 1 |
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人甲 | 1 | 0 | 0 |
工人乙 | 0 | 0 | 0 |
工人丙 | 0 | 3 | 0 |
原始表格
任务1 | 任务2 | 任务3 | |
---|---|---|---|
工人甲 | 1 | 3 | 2 |
工人乙 | 3 | 6 | 5 |
工人丙 | 2 | 8 | 4 |
最终匹配结果:
工人甲 | 任务3 |
---|---|
工人乙 | 任务2 |
工人丙 | 任务1 |
还有一种情况也符合(实际情况很少出现两种结果)
工人甲 | 任务2 |
---|---|
工人乙 | 任务1 |
工人丙 | 任务3 |
sklearn中源码连接:https://github.com/scikit-learn/scikit-learn/blob/0.22.X/sklearn/utils/linear_assignment_.py
c++ 匈牙利匹配算法:https://github.com/mcximing/sort-cpp/blob/master/sort-c%2B%2B/Hungarian.cpp
令矩阵 C 为
现在我们要找最优指派
设:
3.1、某一行减或加一个值、最优结果不变。(第 1 步、第 2 步)
X ( i , j )表示第 i 行第 j 列 当选择让 i 去匹配j时 X ( i , j ) = 1 其余 X ( i , j ) = 0
可以看出两者约束方程相同,最优解必定相同,且最优值相差常数 t 。同理列也是一样
推论:减去每一行每一列减去各行各列的最小元素,得到新的矩阵最优解不变。
3.2、独立 0 元素的最多个数等于能覆盖所有的 0 元素(第 3 步)
独立 0 元素指的是位于不同行不同列的零元素.即同一行,同一列虽然可以有多个0,但它们只能有一个是独立的0元素
这个也比较好理解,每个人只能分配一个工作,一个工作只分配一个人。
3.3、当独立 0 元素小于矩阵的行数时,也就是还有人没有分配到工作时,继续执行 1(第 4 步),直到独立 0 元素等于矩阵行数(第 5 步)。
证明完毕。