11月 17, 2021 | Nix.Huang

背景

网上有很多关于匈牙利算法的文章，要么是介绍计算流程的

每行减去该行最小值
每列减去该列的最小值
使用最少的直线覆盖0元素，如果直线数=n表示找到了最优解，结束，否则执行步骤4.
找出未被直线覆盖的元素的最小值(记为 $\delta$ ), 未被直线覆盖的元素- $\delta$ ，被直线交叉覆盖的元素+ $\delta$ ，执行步骤3

那么是基于增广路径计算最大值的，但是我们常见的应用场景是求最小值呀，怎么也不能用增广路径来解释上面的四步呀，网上找了很多文章，由于不能访问wikipedia, 也浪费了很多时间，直到在emory 大学[参考1] 发现匈牙利算法是一个'primal-dual Simplex method', 开始以为这是一个对偶单纯型法，我学完'Simplex method',然后再学习'dual Simplex method' 发现这两算法还是没法解释匈牙利算法呀，很苦闷，浪费了很多时间后在umich 大学发现参考文档2,才算基本了解这个算法的原理，坑爹呀，原来这算法叫'primal-dual method'，不过前面的东西没有白学，至少多了解两个算法，还了解了一番对偶原理。
将学习和理解记录下来方便有缘人

算法[线性规划]语言描述

算法对偶原理通过线性代数语言不好描述，但是通过二分图可以直观理解：

原问题(primal)

min \ z(x) = \sum_{i=1,j=1}^{i=n,j=n} c_{ij}x_{ij}\\ s.t. \left\{\begin{matrix} \sum_{j=1}^{j=n} x_{ij} = 1 \\ \sum_{i=1}^{i=n} x_{ij} = 1 \\ x_{ij} \geq 0 \\ x_{ij} = 0\ or \ 1 \end{matrix}\right. \\

$x_{ij}$ 是一个置换矩阵，表示行列元素之和为1，且元素只能取0,1， $c_{ij}*x_{ij}$ 表示选取的元素之和

对偶问题(dual)

max \ \sum_{i=1}^{n} u_i + \sum_{j=1}^{n} v_j \\ s.t. \ u_i + v_j \leq c_{ij}

开始ui取一行中最小 $c_{ij}$ , vi 取一列中 $c_{ij}-u_i$ 最小值，
uv可以理解为二分图中两个顶点的值，需要一直满足 $u_i+v_j \leq c_{ij}$
当 $u_i+v_j = c_{ij}$ 取最优解，如果一列或者一行有多个元素满足，由于对偶问题求最大值，那么选 $u_i+v_i$ 最大的那个元素。

增广路径(augmenting path)

可以参考[4][5],5是一个网友通过一个形象的实例演示的，很有才。4是香港科技大学的英文ppt，介绍增广路径及基于增广路径求最大值问题。
简单来说

x\y	y1	y2
x1	1	2
x2	3	5

最优匹配x1-> y1，x2->y1, y1只能匹配一次，所以x1-> y1
全场次优匹配为x1匹配y2,那么就生成路径(增广路径)x2->y1->x1->y2, 这条路径的两个端点都是未匹配的点，将其拆分成两组(x2->y1，x1->y2)，可以看到路径增广了，匹配也发生了反转(原来x1->y1被取代了)

4x4矩阵实例

0	0	0	0
15	22	13	4
12	21	15	7
16	20	22	6
6	11	8	5

每行分别减去4,7,6,5，将减去的数组赋值给ui, 将每列减去1,6,3,0，并将其赋值给vi，得到下面的表格

ui\vi	1	6	3
4	10	12	6
7	4	8	5
6	9	8	13
5	0	0	0

1、元素调整
未被直线覆盖的最小元素=4，未被直线覆盖的元素-4且对应行 $u_i+4$ , 被交叉覆盖元素+4且对应列vi-4,直观解释未被直线覆盖的元素-4是为了寻找增广路径，将次优解的 $c_{ij} =0$ ，因为 $u_i + v_j + c_{ij}^{\prime} = c_{ij}, c_{ij}^{\prime} \geq 0$ , 所以要么将 $c_{ij}$ 扣减量加入ui,要么从vi扣减掉，所以处理第一行的时候决定了v4 = -4, 所以 $c_{44} = 4$ ,解释了算法描述中交叉覆盖元素需要加上 $\delta$ 的原因。
2、寻找增广路径
由于(2,1)位置现在为0，那么第二行原来的(2,4)元素取消选择，现在导致第4列没有元素选中了，所以选择(3,4)元素，一个匹配对变成了两个匹配对，确实增广了

ui\vi	1	6	3	-4
8	6	8	2	0
11	0	4	1	0
10	5	4	9	0
5	0	0	0	4

未被直线覆盖的最小元素=2，未被直线覆盖的元素-2且对应行ui+2, 被交叉覆盖元素+2且对应列vi-2

ui\vi	1	6	3	-6
10	4	6	0	0
11	0	4	1	2
12	3	2	7	0
5	0	0	0	6

最优解为 $\sum_{i=1}^{n} u_i + \sum_{j=1}^{n} v_j = 42$
对应的元素位置为 (1,3)， (2,1)， (3,4)， (4,2)

打赏

如果觉得对你有帮助，请杯啤酒分享你快乐把！，谢谢

参考文档

[1] https://www.mathcs.emory.edu/~cheung/Courses/253/Syllabus/Assignment/algorithm.html
[2] http://www-personal.umich.edu/~murty/books/network_programming/network-3.pdf
[3] https://math.mit.edu/~goemans/PAPERS/book-ch4.pdf
[4] https://cse.hkust.edu.hk/~golin/COMP572/Notes/Matching.pdf
[5] https://blog.csdn.net/sunny_hun/article/details/80627351

Posted in: IT人生

知行合一，止于至善

匈牙利算法原理直观理解

背景