4

我已经查看了解决分配问题的匈牙利算法的几种解释，其中绝大多数都涵盖了非常简单的情况。

我找到的最容易理解的解释是YouTube 视频。

我可以对算法进行编码，但我担心一种特殊情况。如果你看视频的话，31:55到37:42解释了相关案例，但我会在下面解释。

我应该首先提到我将处理一个 300 x 300 的矩阵，所以目视检查是不可能的。此外，我需要找到所有最小分配。换句话说，如果有多个赋值产生相同的最小值，我需要找到它们。

这是我关心的特殊情况。您可以在 YouTube 视频中看到这一点，但我会在这里详细介绍。我们从这个矩阵开始：

3   1   1   4
4   2   2   5
5   3   4   8
4   2   5   9

当我们减少行和列时，我们得到：

0   0   0   0
0   0   0   0
0   0   1   2
0   0   3   4

（让我提一下，我可以直观地看到这个矩阵有 4 个解，总分是 13。）

给定上面的简化矩阵，任何行或列都没有唯一的零，所以，根据视频中描述的算法，我可以任意选择任何零元素进行赋值，所以我选择(1,1)。

我将用星号标记分配的零，并在不再可供考虑的行和列中的那些零旁边放置一个“x”。现在我们有了这个：

0*  0x  0x  0x
0x  0   0   0
0x  0   1   2
0x  0   3   4

接下来，我们继续检查行中是否存在唯一的零。我们在 (3,2) 处找到一个，所以我们用星号标记它，并用“x”标记不可用的零：

0*  0x  0x  0x
0x  0x  0   0
0x  0*  1   2 
0x  0x  3   4

接下来，我们开始在列中寻找唯一的零（因为所有行都已用尽）。我们发现第三列在 (2,3) 处有一个唯一的零，所以我们标记它：

0*  0x  0x  0x
0x  0x  0*  0x
0x  0*  1   2
0x  0x  3   4

此时，没有更多可用的零，并且第 4 行未分配。（这个特定的 YouTube 视频现在使用“滴答程序”，这是确定覆盖所有零所需的最少行数的常用技术。如果您不熟悉这种技术，从14:10到 16 开始解释： 00，尽管演示者使用的矩阵与此处显示的矩阵不同。）“勾选程序”是这样的：

  1. 勾选所有没有分配零的行（第 4 行）。
  2. 对于勾选的每一行，勾选该行中包含零的列。
  3. 对于在步骤 2 中勾选的每一列，勾选已分配零的相应行。
  4. 重复第 2 步和第 3 步，直到无法再打勾为止。
  5. 在所有勾选的列和未勾选的行中画线。

此时，滴答程序生成 4 条垂直线，覆盖全零。四个垂直线告诉我们矩阵中的零代表一个或多个解决方案，但是，正如我们所见，第 4 行是未分配的。尽管有四条垂直线，第四行仍未分配的事实告诉我们，我们选择了错误的零进行分配！

视频的演示者指出这个问题是我们对元素 (1,1) 的初始（任意）分配的结果。演示者说，“有更复杂的方法可用”让我们摆脱这种情况，但他没有解释这些技术是什么。他暗示存在选择零的“智能”方法，而不是我们用来在 (1,1) 处选择零的任意选择。

面对进行任意分配时，我可以采取的一种方法（我不确定它是否是最好的）是从可用任意选择数量最少的行或列进行分配。在此示例中，这意味着我将从只有两个任意选择的第 3 行或第 4 行进行任意分配，而不是从有四个任意选择的第 1 行或第 2 行进行。当然，因为我需要所有正确的解决方案，所以无论何时进行任意分配，我都必须遍历所有可用的任意分配。例如，如果我选择 (3,1) 作为任意分配，我还必须稍后分配 (3,2)。

那么，我的问题是，当我面临任意选择零进行赋值的选择时，最好的方法是什么？是我在上一段中提到的吗？我怎样才能消除如图所示的死胡同？请记住，我仍然需要枚举所有具有相同最低分数的解决方案。

4

1 回答 1

3

一旦对所有行和列执行了减法步骤，就像您所做的那样，算法中有这个步骤，它要求您找到可以删除的最小行数或列数，以便在单元格中不再找到零剩下的（参见维基百科文章中的第 3 步）。如果删除行/列的最小数量等于n，那么您已经到达了一个矩阵，其中可以在所有由零表示的位置进行分配。

您的第二个矩阵就是这种情况。

完成所有可能的减法步骤后，还有这个算法步骤：如果行或列只有一个零，则该零表示（最佳）分配。

我认为这条规则可以概括如下：

如果i行（或列）每个最多有i个零，那么这些零中的i个代表（最佳）分配。

当i为n时，该规则是显而易见的（并且完全没有帮助） 。

但是对于小的i，这可能会有所帮助，尽管查找此类行的算法可能很耗时。在示例问题中，我们发现对于i = 2，该规则适用于第 3 行和第 4 行。该规则还暗示我们可以禁止包含零的列中的任何其他分配。这意味着我们可以将矩阵写为：

-   -   0   0
-   -   0   0
0   0   1   2
0   0   3   4

现在该规则可以再次应用于第 1 行和第 2 行，它们现在也只有 2 个零。

我们看到两个只有零的子矩阵（我们应用规则的主题）：

0   0
0   0

分配任务有两种方式：

x   0
0   x

或者：

0   x
x   0

一般来说，对于具有i行和i列的子矩阵，有 i! 如果它的所有元素都为零，则解决方案，但如果其中一些不是，则更少。

在 concreate 示例中，因此有 2 个！左下子矩阵的解和 2! 对于右上角的矩阵，产生 4 种可能的解决方案。

结论

尽管上述考虑听起来可能很有趣，但我认为搜索此类子矩阵的算法不会比仅以有序方式选择分配并在发现错误时立即回溯的算法更有效追踪。由于您将需要所有解决方案，因此从某一行开始是没有意义的。回溯应该确保算法不会将时间浪费在没有未来的选择上。

于 2016-08-08T20:41:29.870 回答