algorithm - 匈牙利 (Kuhn Munkres) 算法古怪

Question

我已经阅读了这里的每个答案、维基百科和 WikiHow、印度人的演讲和其他来源，我很确定我理解他们在说什么，并且已经按照这种方式实现了。但我对所有这些解释所做出的明显错误的声明感到困惑。

他们都说用最少的行数覆盖矩阵中的零点，如果它等于 N(也就是说，每一行和每一列都有一个零)，那么就有一个零解，我们重做。但后来我发现了这个:

    a  b  c  d  e

A   0  7  0  0  0
B   0  8  0  0  6 
C   5  0  7  3  4 
D   5  0  5  9  3 
E   0  4  0  0  9

每一行和每一列都有一个零，并且没有办法用少于五行的零来覆盖零，但显然没有零的解决方案。 C 行只有 b 列中的零，但 D 行没有零。

我是不是误解了什么？我是否需要更好的测试来确定是否可能存在零分配？所有这些来源都遗漏了一些重要的东西吗？

Answer 1

您可以仅用四行覆盖示例中矩阵中的零:b 列、A 行、B 行、E 行。

这是算法的分步演练，如 the Wikipedia article as of June 25 中所示。应用于您的示例:

    a  b  c  d  e

A   0  7  0  0  0
B   0  8  0  0  6 
C   5  0  7  3  4 
D   5  0  5  9  3 
E   0  4  0  0  9

第 1 步:每行中的最小值为零，因此减法无效。我们尝试分配任务，使每项任务都以零成本执行，但事实证明这是不可能的。继续下一步。

第二步:每一列的最小值也是零，所以这一步也没有作用。继续下一步。

第 3 步:我们找到最少数量的线来覆盖所有零。我们找到 [b,A,B,E]。

    a  b  c  d  e

A   ---|---------
B   ---|---------
C   5  |  7  3  4 
D   5  |  5  9  3 
E   ---|---------

第 4 步:我们找到最小的未覆盖元素。这是 3，位于 (C,d) 和 (D,e)。我们从每个未标记的元素中减去 3，并将 3 加到两行覆盖的每个元素:

    a  b   c  d  e

A   0  10  0  0  0
B   0  11  0  0  6 
C   2  0   4  0  1 
D   2  0   2  6  0 
E   0  7   0  0  9

立即覆盖所有零的最小行数变为 5。这很容易验证，因为每一行都有一个零，每一列都有一个零。该算法断言，现在应该可以在新矩阵上执行与我们在步骤 1 中寻找的任务类似的任务。

我们尝试分配任务，使每项任务都以零成本执行(根据新矩阵)。现在这是可能的。我们找到解决方案 [(A,e),(B,c),(C,d),(D,b),(E,a)]。

我们现在可以返回并验证我们实际找到的解决方案是否是最优的。我们看到每个分配的作业的成本都是零，除了 (C,d)，它的成本是 3。因为 3 实际上是矩阵中最低的非零元素，而且我们已经看到没有零成本的解决方案，很明显这是一个最佳解决方案。