匈牙利算法（也称为Munkres分配算法）

Question

我最近发现了这个算法，但是我很难解释它。该算法在O(n⁴)（显然可以改进为O(n³)）内解决了分配问题，但我不知道原因。

直觉上，我可以看出该算法倾向于找到好的最优解，但我找不到证明！到目前为止，我看到的所有证明都包含我不熟悉的符号。我的问题是：有人能简单而严谨地解释一下吗？

我已经理解了问题可以转换为一个值矩阵，每行和每列必须选择一个值。算法计算所选元素中可能的最小值以及产生该值的选择。显然，找到选择也会找到最小值。

---

我在符号表示方面遇到的困难是这里。在设置部分第三段开始的“让我们称之为函数”...

- PythonPower

---

除非你展示出自己已经做了一些工作的证据，否则你不太可能得到任何帮助 - 也许可以先发布你对算法/证明的理解，并指出你的理解在哪个环节中断。 - Blair Conrad

我也曾经有同样的想法... 但问题在于初始定义，因为使用的符号对我来说是未知的。我不想显得懒惰，但这并不是这种情况！ - PythonPower

另外，我已经删除了作业标签，因为它并不是。我只是对它感兴趣！ - PythonPower

你能贴出你不理解的符号示例吗？ - Grzenio

已完成；抱歉之前没有及时添加。 - PythonPower

Answer 1

您提供的维基百科页面介绍了如何手动在矩阵上执行该算法的步骤。而Python实现也使用了矩阵。有时候，理解算法的唯一方法就是通过手动或交互式控制台逐步进行操作。

- Jweede

---

我已经逐步执行了它，但这并不等同于证明。我有点明白为什么，但这还不够坚实，让我感到满意。 - PythonPower

Answer 2

你可以查看Jungnickel的书，其中包含了对匈牙利算法的彻底理论讨论，从第421页开始，并且还提供了一个例子。通过这个例子，你应该能够看到为什么这个算法是O(n3))的。

- Grembo

Answer 3

这意味着如果在 S 和 T 中 i 和 j 两个位置的 y 值之和小于该位置迄今为止计算出的成本（找到最低潜在答案），那么 S 和 T 的每个位置的 y 值都是潜在答案之一。

如果我没记错的话，这就是动态规划问题。完美匹配指的是当所选人员的最便宜费率正好是他被选中执行的任务时。

- Nerdling

---

我看不到动态规划的方法，但我会更感兴趣！:D - PythonPower

Answer 4

该函数将图中每个顶点映射到有理数系统中，这是由不等式符号Q表示的，该图是S和T的并集，这是U形符号的含义。对于给定的一对顶点，哪部分符号仍然不清楚？

- JB King

---

那么每个边都被赋予了商值...？ - PythonPower

不，这里没有涉及到除法，除非你指的是另一种商的形式。每条边已经被赋予了一个值，即从顶点i到顶点j的c(i,j)。正在定义的函数是y。 - JB King

Answer 5

潜在函数 y 在您完全二分图中为每个顶点分配一个数字，使得任何来自 S（所有人的集合）和 T（所有工作的集合） 的顶点的潜力之和小于连接这些顶点的边的值（因此小于完成工作所需成本）。将0分配给每个顶点的函数是有效潜在函数的好例子。

潜在函数 y 的价值是所有顶点的潜力之和（这是定义）。

可以看出，每个完美匹配的成本至少是每个潜力的价值。

这是相当明显的：在完美匹配中，您必须选择没有共同顶点的 n 条边。每条边的成本都低于其顶点的潜力之和（根据潜力的定义）。当您将来自匹配的所有边的成本总和时，它将高于图的潜力价值。

现在，该算法计算潜力和匹配，使它们的成本/价值相同。由于潜力的价值是问题最小成本的下限，因此您将获得最优解。

这证明了算法的正确性。现在，您需要查看并理解算法为什么以及如何找到成本/价值相等的完美匹配和潜力。

- Grzenio