匈牙利解法

---

资源分派问题的一种特殊解法。

由于是在匈牙利数学家D．Knig研究成果的基础上提出来的，故称匈牙利解法。其一般步骤是：(1)确定独立零。变换给出的效益矩阵C，使其每行每列至少出现一个元素为零，以期从这些零元素的位置上进行分派。假若在变换后的效益矩阵中，某行某列只有一个零元素，这种零称为独立零。(2)划线盖零。以最少的行或列直线，将出现的所有零元素划去盖上。

若最少的直线数m恰好等于分派的方案数n，这时认为出现了足够多的独立零，可进行一对一的完全分派，否则需要进一步变换效益矩阵。(3)进行变换。

在效益矩阵中未划去的元素上减去它们之中的一个最小元素，在第二步盖零直线的交叉处加上该最小元素，其它被划去的元素连同其位置保持不变。

这样变换下去，将会得到足够多的独立零。(4)以零定案。在独立零处施以标号法进行分配，具体先在某列(或某行)只有一个零元素的位置上打标记，同时叉去该零同行(或同列)上的其它零，这样继续下去，即可得到完全的分配方案。