2

我正在尝试按照匈牙利方法中用最少行数覆盖零的步骤，如下所示：

  1. 勾选所有未分配的行。
  2. 如果勾选的行为零，则勾选对应的列。
  3. 在勾选的列中，如果有分配，则勾选对应的行。
  4. 在每个未勾选的行和勾选的列上方画一条线。
  5. 对每个未分配的行重复此操作。
  6. 然后找到 Theta（这是最小的未覆盖值）

问题是当我这样做时，我仍然发现零！导致 Theta 为零并进入无限循环！

例如，如果我们采用以下矩阵 25 x 25)：

1 5 5 2 3 1 2 3 2 4 5 2 3 1 5 5 2 3 1 5 1 4 3 2 5

5 5 3 2 3 2 5 1 4 3 2 5 3 2 4 5 2 5 2 1 1 4 1 2 5

5 1 4 3 2 5 1 1 4 1 2 5 2 2 3 4 1 4 5 3 2 4 5 2 5

1 1 4 1 2 5 3 2 4 5 2 5 5 5 1 5 1 5 5 2 2 3 4 1 4

3 2 4 5 2 5 2 2 3 4 1 4 5 4 2 1 3 2 5 5 5 1 5 1 5

2 2 3 4 1 4 5 5 1 5 1 5 5 5 2 5 5 1 4 5 4 2 1 3 2

5 5 1 5 1 5 5 5 3 2 3 2 1 5 5 1 5 1 5 5 5 2 5 5 1

5 4 2 1 3 2 5 1 4 3 2 5 5 5 4 2 1 3 2 5 1 4 3 2 5

5 5 2 5 5 1 1 1 4 1 2 5 1 5 5 2 5 5 1 1 1 4 1 2 5

2 4 5 3 4 2 3 2 4 5 2 5 2 2 4 5 3 4 2 3 2 4 5 2 5

2 2 5 5 1 3 2 2 3 4 1 4 2 2 2 5 5 1 3 2 2 3 4 1 4

4 1 5 4 5 3 5 5 1 5 1 5 5 4 1 5 4 5 3 5 5 1 5 1 5

5 1 4 3 2 5 3 2 4 5 2 5 5 5 1 4 3 2 5 3 2 4 5 2 5

1 1 4 1 2 5 2 2 3 4 1 4 1 1 1 4 1 2 5 2 2 3 4 1 4

3 2 4 5 2 5 5 5 1 5 1 5 4 3 2 4 5 2 5 5 5 1 5 1 5

2 2 3 4 1 4 5 4 2 1 3 2 1 2 2 3 4 1 4 5 4 2 1 3 2

5 5 1 5 1 5 5 5 2 5 5 1 2 5 5 1 5 1 5 5 5 2 5 5 1

5 1 4 3 2 5 3 5 1 4 3 2 5 3 5 2 2 3 5 2 2 3 2 5 3

3 4 1 4 1 1 1 1 1 4 1 2 5 5 1 4 3 2 5 1 4 1 2 5 2

1 5 5 2 3 1 5 3 2 4 5 2 5 1 1 4 1 2 5 2 4 5 2 5 5

5 5 3 2 3 2 2 2 2 3 4 1 4 3 2 4 5 2 5 2 3 4 1 4 3

5 1 4 3 2 5 2 5 5 1 5 1 5 2 2 3 4 1 4 5 1 5 1 5 5

1 1 4 1 2 5 2 5 4 2 1 3 2 5 5 1 5 1 5 4 2 1 3 2 1

3 2 4 5 2 5 1 5 5 2 5 5 1 5 4 2 1 3 2 5 2 5 5 1 3

2 2 3 4 1 4 1 2 4 5 3 4 2 5 5 2 5 5 1 4 5 3 4 2 2

从匈牙利方法中减去最小行和列值作为步骤 1 和 2 后，我得到：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 4 0 4 0 4 4 4 1 4 4 0 1 4 4 0 4 0 4 4 4 1 4 4 0

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

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

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

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

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

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

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

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

然后当我们进行赋值时，我们将有 23 个赋值而不是 25 个，所以我们根据上述步骤进行前面提到的覆盖零，我会得到以下结果：

粗体单元格是根据上述步骤覆盖的单元格。

请注意，仍然有未发现的零导致无限循环，因为它将在接下来被选中。

请帮我。

先感谢您

4

1 回答 1

0

当每个工人可能完成两项任务时，您可以使用最小成本最大流量算法来解决问题。

首先，让我们看看如何使用 min-cost max flow 解决标准分配问题。创建一个二分图，其中工人在一个部分，任务在另一个部分。在工人 i 和任务 j 之间为所有 i, j 放置一条容量为 1 且成本为 cost_ij 的边。然后将源 S 和来自源的边添加到容量为 1 且成本为 0 的每个工人。类似地，将每个任务的接收器 T 和边添加到具有相同成本和容量的接收器。然后，如果您找到从 S 到 T 的最小成本最大流，那么它的值将是总分配成本。

因此，如果您允许每个工作人员选择两个任务，那么从源到工作人员的边应该具有容量 2。算法的这种添加将以最佳方式解决您的问题，而不管最大差异的给定约束。

但是，目前我不知道对每个可能的输入都有限制的任务的解决方案。如果您的输入值很特殊，您可以在回复中说出来，我们会考虑问题的特殊情况。

于 2013-07-21T22:06:44.330 回答