2)在已打“√”的行中,对该行Ø所在的列打“√”;
3)在已打“√”的列中,对该列○0所在的行打“√”;
4)反复进行2)和3),直到找不出能打“√”的行或列时方可停止;
5)把未打“√”的行和已打“√”的列分别画线,如此便可作出能覆盖全部零元素的最少直线[1].
如果画完直线后还有零元素未被覆盖,说明打“√”错误,需重新来过.转第三步.
第三步 继续变换系数矩阵,然后将其返回第二步.变换方式为:
a) 在没有被直线覆盖的范围内找到最小的元素;
b) 将a)中所述范围内的全部元素都减去该最小元素;
c) 将两条直线交错点的元素均加上这一最小元素;
d) 仅被一条直线覆盖的元素不作任何修改.
重复上述步骤可得最优解,最终确定一种符合题意的最佳解决方案.
匈牙利解法在救援中的应用(3):http://www.youerw.com/shuxue/lunwen_81129.html