匈牙利匹配算法原理以及python实现
from sklearn.utils.linear_assignment_ import linear_assignment## 法1：使用sklearn的模块cost_matrix = np.array([[1，4，7],[2，5，6],[6，7，1]) #这里自己定义indices = linear_assignment(cost_matrix)# indices 是一个n x 2的矩...
原理可参考链接
重：Munkres’ Assignment Algorithm Modified for Rectangular Matrices
Munkres 分配算法
Kuhn-Munkres 算法详细解析
带你入门多目标跟踪（三）匈牙利算法&KM算法
趣写算法系列之–匈牙利算法
匈牙利算法维基百科
【原创】我的KM算法详解
在Python中运行munkres库的复杂性
匈牙利算法和KM算法
匈牙利匹配的用法可以直接调用模块：（输出的结果不一样但都是最大匹配）
from sklearn.utils.linear_assignment_ import linear_assignment
## 法1：使用sklearn的模块
cost_matrix = np.array([[1，4，7],[2，5，6],[6，7，1]) #这里自己定义
indices = linear_assignment(cost_matrix)
# indices 是一个n x 2的矩阵 对应代价矩阵的最大匹配的位置
print(indices)
## 法2：使用scipy的模块
from scipy.optimize import linear_sum_assignment
row_ind, col_ind = linear_sum_assignment(cost_matrix)
print([(x,y) for x,y in zip(row_ind,col_ind)])
# row_ind,col为代价矩阵最佳匹配元素的行号和列号
原理和源代码：
[ 16 26 16 23 40 82 73 35 51 61 15 66 76 98 97 66 7 52 92 65 ] \left[ \begin{matrix} & 16 & 26 &16& 23& 40 \\ & 82& 73& 35& 51& 61 \\ & 15& 66& 76& 98& 97 \\ & 66& 7 &52& 92& 65 \\ \end{matrix} \right] ⎣⎢⎢⎡168215662673667163576522351989240619765⎦⎥⎥⎤
[ 0 10 0 7 24 47 38 0 16 26 0 51 61 83 82 59 0 45 85 58 ] \left[ \begin{matrix} &0 &10 & 0 &7& 24\\ &47& 38& 0&16 &26 \\ &0& 51 &61& 83& 82\\ &59 & 0& 45& 85& 58\\ \end{matrix} \right] ⎣⎢⎢⎡0470591038510006145716838524268258⎦⎥⎥⎤
marked:
[
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
]
\left[ \begin{matrix} &1 &0 &0& 0 &0 \\ &0& 0 &1 &0 &0\\ &0 &0 &0 &0& 0\\ &0 &1& 0 &0& 0\\ \end{matrix} \right]
⎣⎢⎢⎡10000001010000000000⎦⎥⎥⎤
self.marked
[[1 0 0 0 2],
[0 0 1 0 0],
[2 0 0 0 0],
[0 1 0 0 0]]
6 x 7 matrix
原矩阵：
[
80
50
16
77
36
46
1
15
14
44
75
40
85
91
89
16
73
90
10
73
97
87
95
60
58
76
88
48
95
57
68
12
2
19
6
35
24
58
16
36
42
58
]
\left[ \begin{matrix} &80 &50&16&77&36&46& 1\\ &15 &14&44&75&40&85&91\\ & 89&16&73&90&10&73&97\\ &87&95&60&58& 76&88& 48\\ &95&57 &68 &12 &2& 19 & 6\\ &35&24&58 &16 &36 &42 &58\\ \end{matrix} \right]
⎣⎢⎢⎢⎢⎢⎢⎡801589879535501416955724164473606858777590581216364010762364685738819421919748658⎦⎥⎥⎥⎥⎥⎥⎤
行归约：(对第一次匹配的标记一个1
[
79
49
15
76
35
45
0
1
1
0
1
30
61
26
71
77
79
6
63
80
0
1
63
87
39
47
12
10
28
40
0
93
55
66
10
0
17
4
19
8
42
0
1
20
26
42
]
\left[ \begin{matrix} &79& 49 &15 &76 &35& 45& \color{#00f} 0^1 \\ & 1 &\color{#00f}0^1& 30 &61&26& 71 &77\\ & 79& 6 &63& 80& \color{#00f}0^1& 63& 87\\ & 39& 47 &12& 10 &28& 40 & 0\\ & 93& 55& 66 &10 & 0& 17 &4\\ & 19& 8 &42 & \color{#00f}0^1& 20 &26& 42\\ \end{matrix} \right]
⎣⎢⎢⎢⎢⎢⎢⎡791793993194901647558153063126642766180101001352601280204571634017260177870442⎦⎥⎥⎥⎥⎥⎥⎤
self.marked
[[0 0 0 0 0 0 1],
[0 1 0 0 0 0 0],
[0 0 0 0 1 0 0],
[0 0 0 0 0 0 0],
[0 0 0 0 0 0 0],
[0 0 0 1 0 0 0]]
列覆盖后没有0了
减去最小值后（b,1)处为0标记为2
[
78
49
14
76
35
44
0
1
0
0
1
29
61
26
70
77
78
6
62
80
0
1
62
87
38
47
11
10
28
39
0
92
55
65
10
0
16
4
18
8
41
0
1
20
25
42
]
\left[ \begin{matrix} &78 &49 &14& 76& 35& 44&\color{#00f} 0^1\\ &0& \color{#00f}0^1& 29& 61& 26 &70& 77\\ & 78& 6& 62 &80 & \color{#00f}0^1& 62& 87\\ & 38& 47 &11& 10 &28& 39 & 0\\ & 92& 55 &65& 10& 0 &16 &4\\ & 18 &8 &41 &\color{#00f} 0^1& 20 &25& 42\\ \end{matrix} \right]
⎣⎢⎢⎢⎢⎢⎢⎡780783892184901647558142962116541766180101001352601280204470623916250177870442⎦⎥⎥⎥⎥⎥⎥⎤
[
78
49
14
76
35
44
0
1
0
2
0
1
29
61
26
70
77
78
6
62
80
0
1
62
87
38
47
11
10
28
39
0
92
55
65
10
0
16
4
18
8
41
0
1
20
25
42
]
\left[ \begin{matrix} &78 &49 &14& 76& 35& 44&\color{#00f} 0^1\\ &\color{#f00} 0^2 & \color{#00f}0^1& 29& 61& 26 &70& 77\\ & 78& 6& 62 &80 & \color{#00f}0^1& 62& 87\\ & 38& 47 &11& 10 &28& 39 & 0\\ & 92& 55 &65& 10& 0 &16 &4\\ & 18 &8 &41 &\color{#00f} 0^1& 20 &25& 42\\ \end{matrix} \right]
⎣⎢⎢⎢⎢⎢⎢⎡7802783892184901647558142962116541766180101001352601280204470623916250177870442⎦⎥⎥⎥⎥⎥⎥⎤
self.marked
[[0 0 0 0 0 0 1],
[2 1 0 0 0 0 0],
[0 0 0 0 1 0 0],
[0 0 0 0 0 0 0],
[0 0 0 0 0 0 0],
[0 0 0 1 0 0 0]]
再减去最小值后
[
72
43
8
76
35
38
0
1
0
2
0
1
29
67
32
70
83
72
0
2
56
80
0
1
56
87
32
41
5
10
28
33
0
86
49
59
10
0
10
4
12
2
35
0
1
20
19
42
]
\left[ \begin{matrix} &72& 43 &8& 76 &35& 38& \color{#00f} 0^1\\ &\color{#f00} 0^2 & \color{#00f} 0^1& 29& 67& 32 &70& 83\\ & 72 &\color{#f00} 0^2& 56 &80& \color{#00f} 0^1& 56& 87\\ & 32& 41& 5 &10 &28& 33 & 0\\ & 86 &49& 59 &10 & 0& 10 & 4\\ & 12 & 2& 35& \color{#00f} 0^1 &20& 19 &42\\ \end{matrix} \right]
⎣⎢⎢⎢⎢⎢⎢⎡720272328612430102414928295655935766780101001353201280203870563310190183870442⎦⎥⎥⎥⎥⎥⎥⎤
self.marked
[[0 0 0 0 0 0 1],
[2 1 0 0 0 0 0],
[0 2 0 0 1 0 0],
[0 0 0 0 0 0 0],
[0 0 0 0 0 0 0],
[0 0 0 1 0 0 0]]
将第5列置为true后第e,5出现新的0
[
72
43
8
76
35
38
0
1
0
2
0
1
29
67
32
70
83
72
0
2
56
80
0
1
56
87
32
41
5
10
28
33
0
86
49
59
10
0
2
10
4
12
2
35
0
1
20
19
42
]
\left[ \begin{matrix} &72& 43 &8& 76 &35& 38& \color{#00f} 0^1\\ &\color{#f00} 0^2 & \color{#00f} 0^1& 29& 67& 32 &70& 83\\ & 72 &\color{#f00} 0^2& 56 &80& \color{#00f} 0^1& 56& 87\\ & 32& 41& 5 &10 &28& 33 & 0\\ & 86 &49& 59 &10 &\color{#f00} 0^2& 10 & 4\\ & 12 & 2& 35& \color{#00f} 0^1 &20& 19 &42\\ \end{matrix} \right]
⎣⎢⎢⎢⎢⎢⎢⎡7202723286124301024149282956559357667801010013532012802203870563310190183870442⎦⎥⎥⎥⎥⎥⎥⎤
增广路径：
self.marked
[[0 0 0 0 0 0 1],
[2 1 0 0 0 0 0],
[0 2 0 0 1 0 0],
[0 0 0 0 0 0 0],
[0 0 0 0 2 0 0],
[0 0 0 1 0 0 0]]
将增广路径取反,将路径上的1标记为0，路径上的2标记为1，清除覆盖
[
72
43
8
76
35
38
0
1
0
1
0
29
67
32
70
83
72
0
1
56
80
0
56
87
32
41
5
10
28
33
0
86
49
59
10
0
1
10
4
12
2
35
0
1
20
19
42
]
\left[ \begin{matrix} &72& 43 &8& 76 &35& 38& \color{#00f} 0^1\\ &\color{#00f} 0^1 & 0& 29& 67& 32 &70& 83\\ & 72 &\color{#00f} 0^1& 56 &80& 0& 56& 87\\ & 32& 41& 5 &10 &28& 33 & 0\\ & 86 &49& 59 &10 &\color{#00f} 0^1& 10 & 4\\ & 12 & 2& 35& \color{#00f} 0^1 &20& 19 &42\\ \end{matrix} \right]
⎣⎢⎢⎢⎢⎢⎢⎡72017232861243001414928295655935766780101001353202801203870563310190183870442⎦⎥⎥⎥⎥⎥⎥⎤
[[0 0 0 0 0 0 1],
[1 0 0 0 0 0 0],
[0 1 0 0 0 0 0],
[0 0 0 0 0 0 0],
[0 0 0 0 1 0 0],
[0 0 0 1 0 0 0]]
只有5个匹配小于6，除了列覆盖以外减去最小值
[
72
43
3
76
35
33
0
0
0
24
67
32
65
83
72
0
51
80
0
51
87
32
41
0
2
10
28
28
0
86
49
54
10
0
5
4
12
2
30
0
20
14
42
]
\left[ \begin{matrix} &72& 43 & 3& 76& 35& 33& 0\\ & 0 & 0 &24& 67 &32 &65& 83\\ & 72 & 0& 51 &80& 0& 51 &87\\ & 32& 41 & \color{#f00}0^2& 10& 28& 28 & 0 \\ & 86 &49 &54 &10& 0 &5 &4\\ & 12 & 2 &30 &0& 20& 14& 42\\ \end{matrix} \right]
⎣⎢⎢⎢⎢⎢⎢⎡720723286124300414923245102543076678010100353202802033655128514083870442⎦⎥⎥⎥⎥⎥⎥⎤
self.marked
[[0 0 0 0 0 0 1],
[1 0 0 0 0 0 0],
[0 1 0 0 0 0 0],
[0 0 2 0 0 0 0],
[0 0 0 0 1 0 0],
[0 0 0 1 0 0 0]]
进入step5修改2为1
[ 72 43 3 76 35 33 0 1 0 1 0 24 67 32 65 83 72 0 1 51 80 0 51 87 32 41 0 1 10 28 28 0 86 49 54 10 0 1 5 4 12 2 30 0 1 20 14 42 ] \left[ \begin{matrix} &72& 43 & 3& 76& 35& 33& \color{#00f}0^1\\ & \color{#00f}0^1 & 0 &24& 67 &32 &65& 83\\ & 72 & \color{#00f}0^1& 51 &80& 0& 51 &87\\ & 32& 41 & \color{#00f}0^1& 10& 28& 28 & 0 \\ & 86 &49 &54 &10& \color{#00f}0^1 &5 &4\\ & 12 & 2 &30 &\color{#00f}0^1& 20& 14& 42\\ \end{matrix} \right] ⎣⎢⎢⎢⎢⎢⎢⎡72017232861243001414923245101543076678010100135320280120336551285140183870442⎦⎥⎥⎥⎥⎥⎥⎤
[ 80 50 16 77 36 46 1 15 14 44 75 40 85 91 89 16 73 90 10 73 97 87 95 60 58 76 88 48 95 57 68 12 2 19 6 35 24 58 16 36 42 58 ] \left[ \begin{matrix} &80 &50&16&77&36&46& \color{#00f} 1\\ & \color{#00f}15 &14&44&75&40&85&91\\ & 89& \color{#00f}16&73&90&10&73&97\\ &87&95& \color{#00f}60&58& 76&88& 48\\ &95&57 &68 &12 & \color{#00f}2& 19 & 6\\ &35&24&58 & \color{#00f}16 &36 &42 &58\\ \end{matrix} \right] ⎣⎢⎢⎢⎢⎢⎢⎡801589879535501416955724164473606858777590581216364010762364685738819421919748658⎦⎥⎥⎥⎥⎥⎥⎤
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)