设为首页 - 加入收藏
广告 1000x90
您的当前位置:2019年全年最准资料 > 布达佩斯 > 正文

匈牙利算法的步骤

来源:未知 编辑:admin 时间:2019-07-11

  匈牙利算法的步骤:_天文/地理_自然科学_专业资料。匈牙利算法的步骤: 第一步 变换效率矩阵,使各行各列都出现 0 元素。 1°效率矩阵每行元素都减去该行最小元素; 2°效率矩阵每列元素都减去该列最小元素。 第二步 圈出不同行且不同列的 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,已得最优解,计算停,否则转第三步。 第三步 用最少直线°对没有“◎”的行打“√” ; 2°对打“√”行中的 0 元素所在列打“√” ; 3°对打“√”列中“◎”所在行打“√” ; 4°反复进行 2°、 3°,直至打不出新 “√”为止。 5°对没 打“√”的行画横线,对打“√”列画竖线,则效 率矩阵中所有 0 元素被这些直线所覆盖。 第四步 调整效率矩阵,使出现新的 0 元素。 1°找出未被划去元素中的最小元素,以其作为调整量θ ; 2°矩阵中打“√”行各元素都减去θ ,打“√”列各元素 都加θ (以保证原来的 0 元素不变) ,然后去掉所有标记, 转第二步。

本文链接:http://dicaspace.com/budapeisi/2728.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top