本文简单介绍 Hungarian Algorithm(匈牙利算法) 及其矩阵表示下的操作流程。翻译自维基百科。

匈牙利算法(Hungarian Algorithm)是一种组合优化算法(combinatorial optimization algorithm)，用于求解指派问题(assignment problem)，算法时间复杂度为 O(n3) 。Harold Kuhn发表于1955年，由于该算法基于两位匈牙利数学家的早期研究成果，所以被称作“匈牙利算法”。 —— 维基百科

假设有三位工人A, B和C，需要分配他们每人完成一件工作；对于不同的工作他们索要不同的工钱，如下表所示。问题就是要找到一套开销最小的指派方案。

使用匈牙利方法可以找到开销最小的方案，即A负责扫地，B负责擦窗户，C负责清理浴室，总开销为300元。

给定 n 位工人以及n件工作，可以用一个 n×n 的开销矩阵来表示这一指派问题：

算法核心思想：一件大的事物若除去一件小的事物，对这件事没有多大影响。——引自 [ 百度百科 ]

完成后矩阵的每一行至少会出现一个0。假如 a1,b4,c2,d3 是开销矩阵的最小值，则开销矩阵在完成本项操作后变成

然而问题一般并没有这么简单，执行完这一步后，开销矩阵中的0元素很可能没有分布于不同的行列(如下面的矩阵中第三列没有0)，那么继续进行下一步操作。

这一步之后，如果0分布于不同的行列，则得到了最优解；如果以每个0为中心画十字(见下图)、被十字覆盖的其余0不再画十字，所有的0都画十字后仍有元素未被覆盖(图中 c3 )，则说明指派未完成，继续进行下一步。

3.1把任务尽可能多的分配给工人 (1)第一行(表示第一个人工可接受的任务)有一个0，所以把第1项任务分配给工人 a 。由于第1项任务已经分配出去，所以位于第三行第一列的0不再被考虑。 (2)第二行有一个0，所以把第4项任务分配给工人b。 (3)第三行原本有一个0，但是由于第1项任务已经被分配出去，所以不予以考虑，不能给 c 分配任务。 (4)第四行有两个未被覆盖的0，但只能给d分配一项任务，另一项未被分配的任务要划掉、本轮不予以考虑。 3.2 用最少的线覆盖所有0 3.2.1标记所有上一步后仍未得到任务的工人（矩阵的行）：标记第三行 3.2.2标记所有**刚被标记过的行中**0所在的列：标记第一列 3.2.3标记所有刚被标记过的列中0所在的行：标记第一行 3.2.4对仍未得到任务的工人(矩阵的行)重复以上3步 3.2.5在所有标记过的列和未标记的行上画线 经过以上画线操作，所有的0就被以最少的线覆盖了。

被覆盖元素中的最小值实际上是完成所有任务过程中不可避免的开销。 这一步的作用是增加开销矩阵中0的个数，使得任务更易分配。