匈牙利算法的步骤：.doc

《匈牙利算法的步骤：.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、匈牙利算法的步骤：第一步变换效率矩阵，使各行各列都出现0元素。1°效率矩阵每行元素都减去该行最小元素；2°效率矩阵每列元素都减去该列最小元素。第二步圈出不同行且不同列的0元素，进行试指派。1°（行搜索）给只有一个0元素的行中的0画圈，记作“◎”，并划去与其同列的其余0元素；2°（列搜索）给只有一个0元素的列中的0画圈，记作“◎”，并划去与其同行的其余0元素；3°反复进行1°、2°，直至所有0元素都有标记为止。4°若行（列）的0元素均多于一个，则在0元素最少的行（列）中选定一个0元素，标“◎”,并划

2、去与其同行同列的其余0元素。5°若不同行且不同列的“◎”已达n个，则令它们对应的xij=1，其余xij=0，已得最优解，计算停，否则转第三步。第一步变换效率矩阵，使各行各列都出现0元素。1°效率矩阵每行元素都减去该行最小元素；2°效率矩阵每列元素都减去该列最小元素。第二步圈出不同行且不同列的0元素，进行试指派。1°（行搜索）给只有一个0元素的行中的0画圈，记作“◎”，并划去与其同列的其余0元素；2°（列搜索）给只有一个0元素的列中的0画圈，记作“◎”，并划去与其同行的其余0元素；3°反复进行1°、

3、2°，直至所有0元素都有标记为止。4°若行（列）的0元素均多于一个，则在0元素最少的行（列）中选定一个0元素，标“◎”,并划去与其同行同列的其余0元素。5°若不同行且不同列的“◎”已达n个，则令它们对应的xij=1，其余xij=0，已得最优解，计算停，否则转第三步。第三步用最少直线覆盖效率矩阵中的0元素。1°对没有“◎”的行打“√”；2°对打“√”行中的0元素所在列打“√”；3°对打“√”列中“◎”所在行打“√”；4°反复进行2°、3°，直至打不出新“√”为止。5°对没打“√”的行画横线，对打“√

4、”列画竖线，则效率矩阵中所有0元素被这些直线所覆盖。第四步调整效率矩阵，使出现新的0元素。1°找出未被划去元素中的最小元素，以其作为调整量θ；2°矩阵中打“√”行各元素都减去θ，打“√”列各元素都加θ（以保证原来的0元素不变），然后去掉所有标记，转第二步。