匈牙利算法讲解

匈牙利算法介绍

匈牙利算法(Hungarian Algorithm)，该算法使用来解决分配问题或者指派问题，比如我们在工作中，给设备分配任务或者给工人分配工作等。我们希望可以通过最优化的方式，使得最小化总的成本代价(total cost)

图中左边是works，右边是jobs，我们希望对works分配jobs，这就是二分图匹配。使得总的成本最小。分配的可能性非常多，如果是暴利求解的话，计算代价会非常大。

匈牙利算法：是一种在多项式时间内求解任务分配问题的组合优化算法,最初是由一名匈牙利数学家提出来的，所以称为匈牙利算法。

数学建模中常见的任务分配问题，有时也叫做婚配问题，这是一个整数线性规划的问题，一般使用匈牙利算法进行求解。N个人分配N项任务，一个人只能分配一项任务，一项任务只能分配给一个人，将一项任务分配给一个人是需要支付报酬，如何分配任务，保证支付的报酬总数最小。具体问题有有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？

举例说明

例子1. 假设有4个起重机(cranes),总共有4项任务，每个crane必须分配一项任务。表中数据显示了每