匈牙利算法的步骤

步骤一:将关联矩阵每一行减去本行的最小值,进入步骤二。

步骤二:将新的矩阵每一列减去本列的最小值,进入步骤三。

步骤三:用最少的行线和列线将新矩阵中的零全部穿起来,检查目前是否为最优分配。如果行线和列线没有将矩阵所有元素都穿起来,进入第四步,否则则进入步骤五

步骤四:将行线和列线没有穿起来的元素中找到最小元素,将剩余元素减去最小元素,对应行线和列线的交叉点的元素加上最小元素,

步骤五:找出每一行对应的0元素和列对应的0元素,根据0元素找到最优分配。

 

 

例子

原始矩阵

匈牙利算法的步骤

步骤一

匈牙利算法的步骤

步骤二

匈牙利算法的步骤

步骤三

匈牙利算法的步骤

步骤四

匈牙利算法的步骤

匈牙利算法的步骤

步骤5

匈牙利算法的步骤匈牙利算法的步骤