匈牙利算法matlab理论

匈牙利算法是一种关于指派问题的求解方法，最早由库恩在1955年提出。它通过修正效益矩阵的行或列，使得每一行或列中至少有一个零元素，然后得到与这些零元素相对应的一个完全分配方案，从而达到最优分配的目标。该算法的理论基础是，在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最优分配。其求解步骤如下：

1. 修正效益矩阵，使之变成每一行和每一列至少有一个零元素的缩减矩阵：
- 从效益矩阵的每一行元素减去各该行中最小元素；
- 再从所得缩减矩阵的每列减去各该列的最小元素。

2. 试制一个完全分配方案，它对应于不同行不同列只有一个零元素的缩减矩阵，以求得最优解：
- 如果得到分布在不同行不同列的N个零元素，那么就完成了求最优解的过程。结束。
- 如果所分布于不同行不同列中的零元素不够N个，则转下一步。

3. 作出覆盖所有零元素的最少数量的直线集合：
- 标记没有完成分配的行。
- 标记已标记行上所有未分配零元素所对应的列。
- 对标记的列中，已完成分配的行进行标记。
- 重复上述两个步骤直到没有可标记的零元素。
- 对未标记的行和已标记的列画纵、横线，这就得到能覆盖所有零元素的最少数量的直线集合。

4. 修改缩减矩阵，以达到每行每列至少有一个零元素的目的：
- 在没有直线覆盖的部分中找出最小元素。
- 对没有画直线的各元素都减去这个元素。
- 对画了横线和直线交叉处的各元素都加上这个最小元素。
- 对画了一根直线或横线的各元素保持不变。
- 转第二步。

匈牙利算法在实际应用中被广泛使用，并且具有较快的仿真速度。如果需要在MATLAB中实现匈牙利算法，可以通过下载相关代码来实现。