最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • Hungarian Algorithm分析与解释

    在阅读DeTr系列One to One的检测算法的时候,您肯定遇到过“Hungarian Algorithm(匈牙利算法)”。该算法的作用是解决样本的分配问题(Assignment Problem),即对预测框分配最优的groud truth。本文将介绍分配问题以及如何使用“匈牙利算法”解决它。

    01

    分配问题

    1.1 什么是分配问题?

    设n个代理和n个任务,可以分配任何代理以执行任何任务,这会产生一些费用,该费用可能会因代理任务分配而异。 而分配问题要求执行所有任务时,以分配的总成本最小化为目的,将每个任务恰好分配给一个代理。

    分配问题需要确保以下几点:

    • 任务和代理的数量应相同;

    • 每个代理应仅分配一个任务,每个任务应仅分配一个代理;

    • 需要找到一种可行的解决方案,它将消耗最小的成本。

    一文掌握Hungarian Algorithm

    分配问题可以应用在很多场景,如:

    • 将机器分配给工厂订单。

    • 将销售/营销人员分配到区域。

    • 指派老师上课。

    • 将警车分配到巡逻区。

    1.2 例子

    问题:在一个建筑工地中,有4台起重机,每台起重机必须分配一个工作。下表显示了每台起重机的每项工作所需的时间。 为工作找到最佳的起重机分配,以使完成工作所需的时间最短。

    一文掌握Hungarian Algorithm

    高亮显示的框显示最佳的分配。最优分配如下:

    一文掌握Hungarian Algorithm
    1.3 解决分配问题的几种方法

    方法1:暴力搜索

    在这里,我们一一尝试所有组合以找到最佳解决方案。这是一种乏味的方法,因为随着任务和起重机数量的不断增加,计算的数量也随之增加。复杂度为n!这是非常低效的。

    一文掌握Hungarian Algorithm

    方法2:贪婪方法

    在这种情况下,算法将选择最低成本的工人分配第一个任务,然后选择下一个成本最低的工人,依此类推,直到所有任务都已分配。贪婪算法试图通过迭代地改进候选解来接近最优解,但不能保证会真正找到最优解。

    方法3:图方法

    如果我们使用图来表述问题,该算法将更易于描述。我们有一个完整的图G =(S,T; E),其中包含n个工人顶点S和n个作业顶点(T),并且每个边的成本均为c(i,j)。我们希望找到一个总成本最低的完美匹配。

    方法4:匈牙利算法

    匈牙利算法是一种组合优化算法,它是解决多项式时间复杂度问题的较快方法。

    下面,我们就来看看匈牙利算法。

    02

    Hungarian Algorithm

    匈牙利算法的流程如下:

    1.从每一行中找到最小元素,然后从该行的所有元素中减去该值

    2.从每列中找到最小元素,然后从该列中所有元素中减去该值;

    3.令m =覆盖表中所有零所需的最小行数;

    4. while(m!=覆盖表中所有零所需的最小列数)

    • 从发现的元素中找到最小的元素

    • 从所有其他未发现的元素中减去该元素

    • 将此元素添加到线条相交的元素中

    • 寻找新的

    5.使用零来分配可能的组合,即:只要存在零,就可以分配任务;

    6.找到最低成本;

    7.结束。

    现在,我们以前面建筑工地的问题为例,使用匈牙利算法解决该问题。

    步骤1:从每一行中找到最小值,然后从所有其他行元素中减去它;

    一文掌握Hungarian Algorithm
    一文掌握Hungarian Algorithm

    步骤2:从每列中找到最小值,然后从所有其他列元素中减去它;

    一文掌握Hungarian Algorithm
    一文掌握Hungarian Algorithm

    步骤3:找出覆盖所有零的最小行数;

    一文掌握Hungarian Algorithm

    正如我们看到的那样,当我们在第1列和第2列以及第3行上绘制线时,表的所有零都被覆盖了,但行数不等于列数。

    步骤4-1:从未发现的元素中找到最小元素,并从其余未发现的元素中减去它,然后将其添加到相交的元素中。

    一文掌握Hungarian Algorithm
    一文掌握Hungarian Algorithm

    步骤4-2:找到覆盖所有零的最小行数。

    一文掌握Hungarian Algorithm

    现在我们看到在第1行,第2行和第2列绘制线时,所有零都被覆盖了。但是行数(m)仍然不等于列数(n),因此我们再次重复步骤4。

    步骤4-1-1:从未发现的元素中找到最小值,然后从其余未发现的元素中减去最小值,然后将该元素添加到线条相交的元素中。

    一文掌握Hungarian Algorithm
    一文掌握Hungarian Algorithm

    步骤4-2-2:找到覆盖所有零的最小行数。

    一文掌握Hungarian Algorithm

    现在我们看到,在第1行,第2行,第3行,第4行绘制垂直线时,我们已经覆盖了最小行数中的所有零。现在我们的行数(m)=行数/列数(n)= 4,因此我们已经找到了最优解。

    第5步:使用零来分配可能的组合-只要存在零,就可以将任务分配给相应的业务代表。

    一文掌握Hungarian Algorithm
    一文掌握Hungarian Algorithm

    步骤6:找出费用。

    一文掌握Hungarian Algorithm

    如上,最低成本为19,与我们在先前示例中获得的解决方案相符。因此,我们已经找到解决方案。

    注意:使用上述步骤获得的表中的零的其他组合,也能带来相同的最低成本。如下,表1的总费用= 5 + 3 + 5 + 6 = 19,表2的总费用= 4 + 8 + 4 + 3 = 19

    一文掌握Hungarian Algorithm
    一文掌握Hungarian Algorithm
    好了,本文就到这里了,希望在阅读此博客后,您会清楚分配问题和匈牙利算法的概念!
    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » Hungarian Algorithm分析与解释

    发表评论

    • 52会员总数(位)
    • 320资源总数(个)
    • 25本周发布(个)
    • 3 今日发布(个)
    • 333稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情