如何使用匈牙利算法(use the hungarian algorithm)
台阶
- 1在矩阵中排列信息，左侧为“人员”，顶部为“活动”，中间为每对的“成本”。
- 2如有必要，通过添加虚拟行/列来确保矩阵为正方形。按照惯例，虚拟行/列中的每个元素都与矩阵中的最大数相同。
- 3通过从行中减去每行的最小值来减少行数。
- 4如果有没有零的列，则通过从该列中减去每列的最小值来减少列数。
- 5.以尽可能少的行数覆盖零元素。（如果行数等于行数，则转至步骤9）
- 6在每个覆盖元件上添加最小未覆盖元件。如果一个元素被覆盖了两次，则将最小元素添加到该元素中两次。
- 7从矩阵中的每个元素中减去最小元素。
- 8再次覆盖零元素。如果覆盖零元素的行数不等于行数，请返回步骤6。
- 9通过选择一组零来选择匹配项，以便每行或每列仅选择一个。
- 10将匹配应用于原始矩阵，忽略伪行。这表明谁应该做哪项活动，加上成本将得到总的最低成本。
- 如果希望找到最大匹配而不是最小匹配，请在步骤1中将每个数字乘以-1，然后按照所写的步骤进行操作。
- 这里的一个关键观点是，将相同的数字添加到矩阵的一行或一列中的所有条目中，会生成具有相同最优解的新矩阵。这就是为什么我们可以在第6步中简化矩阵。
- 发表于 2022-05-08 01:47
- 阅读 ( 67 )
- 分类：教育
你可能感兴趣的文章
适应的(adaptive)和非自适应路由算法(non adaptive routing algorithms)的区别
...应路由算法 5. 摘要 什么是自适应路由算法(adaptive routing algorithms)？ 动态路由或自适应路由使用自适应算法。这些算法根据拓扑结构和网络流量改变路由决策。相邻路由器或所有路由器提供路由信息。主要的优化参数是一些跳数...
算法(algorithm)和流程图(flowchart)的区别
...列比较-算法与表格形式的流程图 6. 摘要 什么是算法(an algorithm)？ 每一个任务都是根据一个算法来完成的。如果Facebook有一个这样的问题，那么它将如何在一个日志中出现。首先，用户应该打开浏览器。然后他应该输入正确的网...
在youtube上发现新内容的好方法
...auto-generated channels of trending and popular videos that are created by algorithms. On these channels, you'll see a notice in the "About" section that they've been auto-generated by YouTube. YouTube's auto-generated channels have "Topic" as a suffix. ...
你所说的：你如何记录你的密码
...ember – needs to make a string that is at least 50 characters long 2) an algorithm that allows you to get a set of characters from that set of words – such as every ‘n’ characters 3) write down the start point in that string, and the value of ‘n’ that you will use and the number of chara...
斯坦福算法决定在5000剂疫苗中，只给7名一线covid-19工作者接种疫苗
... chief resident to other residents, Stanford’s leaders explained that an algorithm was used to assign its first allotment of the vaccine. The algorithm was said to have prioritized those health care workers at highest risk for COVID infecti***, along with factors like age and the location or unit ...
什么是伪码(what is the pseudocode)和算法？(algorithm?)的区别
简单来说，伪代码是一种描述算法逻辑的叙述。 伪代码不是可执行代码，因此不必使用精确的语法；但是，遵循业界广泛使用的标准是很有帮助的，解决方案团队可以很容易地理解该标准。 统一建模语言（UML）和其他业务...
dda公司(dda)和bresenham算法(bresenham’s algorithm)的区别
...实际差异。 什么是数字差分算法（dda）(digital differential algorithm (dda))？ DDA主要用于在计算机图形学中绘制线，在预测下一个像素值时使用实际值。假设初始像素值为（X0，Y0）（X0，Y0），目标像素为（X1，Y1）（X1，Y1）。我们将...
算法(algorithm)和伪码(pseudocode)的区别
...区别的比较 关键术语 算法，伪代码，编程 什么是算法(algorithm)？ 算法是一个逐步解决问题的过程。过程是一个有限的指令序列，每个指令在有限的时间内执行。每一个问题都可以借助一个算法来解决。例如，当用户想要登录...
遗传算法(genetic algorithm)和传统算法(traditional algorithm)的区别
...、搜索、排序、分治、传统算法 什么是遗传算法(genetic algorithm)？ 遗传算法是指基于遗传和自然选择的一类算法。这与物种适应环境变化并能够生存的过程相似。换句话说，它是建立在生物进化的基础上的。 此外，该算法不断...
剩下的一天：谷歌调整他们的算法以获得更好的结果，lifehacker六岁了
...am, and we've enjoyed every second of it. Thanks for reading! [@lifehacker]Algorithm change launched Google's altered their search algorithm to rank the original source of content higher—a change that will hopefully help fight their battle against splogs. [Matt Cutts]Skype 5 for Mac intentionally ...
0 篇文章
