algorithm - 匈牙利算法(也是 Munkres 的分配算法)

Question

我偶然发现了 this algorithm最近，我很难向自己解释。该算法解决了 assignment problem在 O(n⁴) 中(显然可以改进到 O(n³))但我不明白为什么。

凭直觉，我可以看出该算法会倾向于找到最佳解决方案，但我看不到证明!到目前为止我看到的所有证明都包含我不熟悉的符号。我的问题是:任何人都可以严格而简单地解释一下吗？

我已经知道问题可以转移到一个值矩阵，其中必须在每一行和每一列中选择一个值。可能的最小值(来自所选元素)和产生的选择是算法计算的内容。显然找到选择也找到了最小值。

---

我在符号方面苦苦挣扎的部分是 here . 设置部分的第三段开始“让我们调用一个函数”...

Answer 1

Wikipedia page您链接到的有关于如何在矩阵上手动执行此算法的步骤。 python implementation也使用矩阵。有时，理解算法的唯一方法是手动或在交互式控制台中逐步执行。