匈牙利算法介绍 - 知乎

　　在阅读DeTr系列One to One的检测算法过程，您肯定遇到过“匈牙利算法”算法，其需要对预测框分配最优的groud truth？ 也就是分配问题！ 本文将介绍分配问题以及如何使用“匈牙利算法”解决它。

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

　　我们需要确保以下几点：任务和代理的数量应相同。每个代理应仅分配一个任务，每个任务应仅分配一个代理我们想找到一种可行的解决方案，它将消耗最小的成本

　　例子

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

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

　　分配问题的很少应用是：将机器分配给工厂订单。将销售/营销人员分配到区域。指派老师上课。将警车分配到巡逻区。

　　方法1：蛮力

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

　　方法2：贪婪方法

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

　　方法3：图方法

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

　　方法4：匈牙利算法

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

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

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

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

　　4. while（m！=覆盖表中所有零所需的最小列数）从发现的元素中找到最小的元素从所有其他未发现的元素中减去该元素将此元素添加到线条相交的元素中寻找新的

　　5.使用零来分配可能的组合，即：只要存在零，就可以分配任务；

　　6.找到最低成本；

　　7.结束。

　　使用匈牙利问题解决示例

　　我们以前面的示例问题为例，使用匈牙利算法解决该问题。

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

　　步骤2：从每列中找到最小值，然后从所有其他列元素中减去它；

　　步骤3：找出覆盖所有零的最小行数；

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

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

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

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

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

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

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

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

　　步骤6：找出费用。

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

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

　　希望在阅读此博客后，您会清楚分配问题和匈牙利算法的概念！

　　翻译自：

　　https://medium.com/@riya.tendulkar16/the-assignment-problem-using-hungarian-algorithm-4f105729af18

　　更多干货都在公众号，扫描下方二维码关注吧