最优化学习中的匈牙利算法.docx

匈牙利算法 海风与甜橙 计算步骤 列出单价运算表。 找出各个行中的最小值，分别每行分别减去该行的最小值；其次，找出各个列的最小值，每一列减去该列相对应的最小值。 通过第二步，会得到一部分的0值，我们对这一部分的0值，进行运算即：找出唯一只有一个0的行，将这个0圈出，并将有这个0的这一列划去，对剩余部分的找出唯一只有一个0的列，将这个0圈出，将有0的这一行划去。 重复步骤三，知道所有0都被找出。 若被圈出0的个数与行（列）数m相同即为最优解。 若小于m，找出剩余数中的最小值k，没被划去的每行的ui=k，其余为0，没被划去的每列的vj=0，其余为-k，用每一个值减去对应行列的ui,vj. 重复步骤6，直至被圈出0的个数等于m，即找到最优解。 例题 有一份说明书, 要分别译成英、日、德、俄四种文字, 交甲乙丙丁四个人去完成. 因各人专长不同, 他们完成翻译不同文字所需的时间如表所示. 应如何分配, 使这四人分别完成 这四项任务总的时间最少.