《匈牙利算法的步骤：(共2页).doc》由会员分享，可在线阅读，更多相关《匈牙利算法的步骤：(共2页).doc（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上匈牙利算法的步骤：第一步 变换效率矩阵，使各行各列都出现 0 元素。 1效率矩阵每行元素都减去该行最小元素； 2效率矩阵每列元素都减去该列最小元素。 第二步 圈出不同行且不同列的 0 元素，进行试指派。 1（行搜索）给只有一个0 元素的行中的0 画圈，记作“”，并划去与其同列的其余0元素； 2（列搜索）给只有一个0 元素的列中的0 画圈，记作“”，并划去与其同行的其余0元素； 3反复进行1、2，直至所有0元素都有标记为止。 4若行（列）的0元素均多于一个，则在0元素最少的行（列）中选定一个0元素，标“”,并划去与其同行同列的其余0元素。 5若不同行且不同列的 “”已达
2、n个，则令它们对应的xij =1，其余xij =0，已得最优解，计算停，否则转第三步。第一步 变换效率矩阵，使各行各列都出现 0 元素。1效率矩阵每行元素都减去该行最小元素；2效率矩阵每列元素都减去该列最小元素。第二步 圈出不同行且不同列的 0 元素，进行试指派。1（行搜索）给只有一个0 元素的行中的0 画圈，记作“”，并划去与其同列的其余0元素；2（列搜索）给只有一个0 元素的列中的0 画圈，记作“”，并划去与其同行的其余0元素；3反复进行1、2，直至所有0元素都有标记为止。4若行（列）的0元素均多于一个，则在0元素最少的行（列）中选定一个0元素，标“”,并划去与其同行同列的其余0元素。5若不同行且不同列的 “”已达n个，则令它们对应的xij =1，其余xij =0，已得最优解，计算停，否则转第三步。第三步 用最少直线覆盖效率矩阵中的0元素。1对没有“”的行打“”；2对打“”行中的0元素所在列打“”；3对打“”列中“”所在行打“”；4反复进行2、 3，直至打不出新 “”为止。5对没 打“”的行画横线，对打“”列画竖线，则效率矩阵中所有0元素被这些直线所覆盖。第四步 调整效率矩阵，使出现新的0元素。1找出未被划去元素中的最小元素，以其作为调整量；2矩阵中打“”行各元素都减去，打“”列各元素都加（以保证原来的0元素不变），然后去掉所有标记，转第二步。 专心-专注-专业