2

我正在关注印度人在 Youtube 上关于匈牙利问题的教程。我在他决定下一步要选择哪些行和列的地方进行堆叠。他的例子没有我面临的问题。这是我的示例表：

2 1 0 0 0 3
2 0 4 5 2 7
0 7 0 0 0 5
3 2 3 1 2 0
0 0 6 3 3 5
3 4 5 2 0 3

所以让我们一步一步开始行和列的选择：

  1. 第一行包含 >1 个零 => 转到下一行
  2. 选择 (2,1) 零并将 (5,1) 添加到暂停的零
  3. 第三行包含 >1 个零 => 转到下一行
  4. 选择 (4,6) 零
  5. 选择 (5,1) 零并将 (3,1) 添加到暂停的零
  6. 选择 (6,5) 零并将 (3,5), (1,5) 添加到暂停的零

现在，剩下的零是 (1,3), (1,4), (3,3), (3,4)

我找不到处理它们的方法，也找不到按列或按行的方法。我该怎么处理它们？

这是最后的表格：

2     1     0?    0?    0(su) 3
3     0(se) 4     5     2     7
0(su) 7     0?    0?    0(su) 5
3     2     3     1     2     0(se)
0(se) 0(su) 6     3     3     5
3     4     5     2     0(se) 3

在哪里

  • su=暂停
  • se=选中
  • ? = 我应该做什么
4

1 回答 1

1

在这个特定的例子中，我们可以任意选择一个 0。选择左上角的给我们

2     1     0(se) 0(su) 0(su) 3
3     0(se) 4     5     2     7
0(su) 7     0(su) 0?    0(su) 5
3     2     3     1     2     0(se)
0(se) 0(su) 6     3     3     5
3     4     5     2     0(se) 3

然后我们可以选择最终的空闲 0 并完成。

但这并不总是有效。考虑

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

（如果您更喜欢视频，我使用与此处相同的问题，尽管我会实际解决它。）

我们不能从一开始就选择任何东西，所以我们随意选择第一个 0。

0(se) 0(su) 0(su) 0(su)
0(su) 0     0     0
0(su) 0     1     2
0(su) 0     3     4

现在我们可以选择 (1,3)，因为它是该行中唯一的空闲 0。

0(se) 0(su) 0(su) 0(su)
0(su) 0(su) 0     0
0(su) 0(se) 1     2
0(su) 0(su) 3     4

然后是 (3,1)，因为它是其列中唯一的空闲 0。

0(se) 0(su) 0(su) 0(su)
0(su) 0(su) 0(se) 0(su)
0(su) 0(se) 1     2
0(su) 0(su) 3     4

这给了我们 3 个总分配，但我们需要 4 个作为解决方案，并且没有更多可用的 0 可以分配。此时可能没有解决方案，因此我们需要继续使用匈牙利算法进行画线步骤。

G. Srinivasan 教授在我链接的视频中介绍了这一点，所以我会跳到结果。如果绘制的线数多于我们正在寻找的作业数，我们继续适当地使用匈牙利算法的其余部分；如果小于，说明上一步出了问题，你应该回去检查你的工作；但是如果它是相等的（就像在这个例子中一样），那么我们知道这里有一个我们还没有找到的最优解。

我对有问题的任意分配的解决方案是更任意的分配。第 4 行是目前唯一没有赋值的行，所以我们将从那里开始并分配它的第一个 0（暂停的 0 现在无关紧要，所以我没有标记它们）。

0(se) 0     0     0
0     0     0(se) 0
0     0(se) 1     2
0(se) 0     3     4

这显然是有问题的，因为我们已经在第一列中进行了分配。为了解决这个问题，我们需要将其中一个移动到其他地方。幸运的是第 4 行仍然没有赋值，并且 (1,4) 是零，所以我们可以将 (1,1) 中的赋值移动到 (1,4)。

0     0     0     0(se)
0     0     0(se) 0
0     0(se) 1     2
0(se) 0     3     4

现在没有冲突，我们有 4 个作业，所以这是我们的解决方案。

于 2016-06-09T00:32:37.520 回答