匈牙利算法（Kuhn Munkres算法）的奇特性

Question

3

我已经阅读了所有的回答、维基百科和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行。

我是否在这里有误解？我需要更好的测试来判断是否可能存在零分配吗？所有这些来源是不是都遗漏了一些关键信息？

- Lee Daniel Crocker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- svk · Accepted Answer

您可以用四条线覆盖您示例中矩阵中的零：列 b，行 A，行 B，行 E。

以下是按照维基百科6月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：每行的最小值为零，因此减法没有影响。我们尝试分配任务，使得每个任务都以零成本完成，但结果证明这是不可能的。继续进行下一步。

步骤2：每列中的最小值也是零，因此这一步也没有影响。继续进行下一步。

步骤3：我们找到了一个覆盖所有零的最小线条。我们发现[b,A,B,E]。

    a  b  c  d  e

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

第四步：我们找到最小未覆盖元素。在(C,d)和(D,e)处，这是3。我们从每个未标记的元素中减去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实际上是矩阵中最低的非零元素，并且我们已经看到没有零成本的解决方案，因此显然这是一个最优解。