1

我正在尝试实施匈牙利算法。检查维基百科的步骤：https ://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation

考虑以下输入 (10 x 10)：

x x 0 x 0 x 0 x x x
x x 0 x x x x x x x
0 0 x x x x x 0 x x
x x x x x 0 x x x x
x x x x x 0 x x x x
x x x 0 0 x x x x x
0 x x x x x x x x x
x x x x x x x x 0 0
x x x x x x x x x 0
x x x x x x x x 0 x

它需要 8 行来覆盖所有零（从 0 开始索引的行和列）：R0 R1 R2 R5 C0 C5 C8 C9。

但是，请遵循维基百科中给出的步骤：

  1. 将零标记为“已分配”或“划掉”。已分配：(0, 2)，划掉：(0, 4) (0, 6) (1, 2)；已分配：(2, 0)，划掉：(2, 1) (2, 7) (6, 0)；已分配：(3, 5)，划掉：(4, 5)；已分配：(5, 3)，划掉：(5, 4)；已分配：(7, 8)，划掉：(7, 9) (9, 8)；已分配：(8, 9)。
  2. 标记所有没有分配的行：R1 R4 R6 R9；在新标记的行中标记所有具有零的列：C2 C5 C0 C8；在新标记的列中标记所有具有分配的行：R0 R3 R2 R7。
  3. 重复2中的最后两步，直到没有行或列可以被标记：在新标记的行中标记所有具有零的列：R0->C4 C6，R3->none，R2->C1 C7，R7->C9；在新标记的列中标记所有具有分配的行：C4 C6 C1 C7->none，C9->R8。

现在除了 R5 之外的所有行都被标记了；除 C3 外的所有列均已标记。覆盖所有零所需的行数将是 9 垂直 + 1 水平 = 10，这是不正确的。

谁能告诉我在哪里犯了错误？或者获得最小线的算法本身是不完美的？

4

0 回答 0