匈牙利算法的步骤
步骤一:将关联矩阵每一行减去本行的最小值,进入步骤二。
步骤二:将新的矩阵每一列减去本列的最小值,进入步骤三。
步骤三:用最少的行线和列线将新矩阵中的零全部穿起来,检查目前是否为最优分配。如果行线和列线没有将矩阵所有元素都穿起来,进入第四步,否则则进入步骤五
步骤四:将行线和列线没有穿起来的元素中找到最小元素,将剩余元素减去最小元素,对应行线和列线的交叉点的元素加上最小元素,
步骤五:找出每一行对应的0元素和列对应的0元素,根据0元素找到最优分配。
例子
原始矩阵
步骤一
步骤二
步骤三
步骤四
步骤5