匈牙利算法死胡同
Hungarian algorithm dead end
我正在学习 Youtube of the Indian guy about the Hungarian problem 上的教程。我堆叠在他决定下一步将 select 编辑哪些行和列的位置。他的例子没有我面临的问题。这是我的示例的 table：
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
所以让我们一步步开始行和列selection:
- 第一行包含 >1 个零 => 转到下一行
- select (2,1) 归零并将 (5,1) 添加到悬浮的零
- 第三行包含 >1 个零 => 转到下一行
- select (4,6) 零
- select (5,1) 归零并将 (3,1) 添加到悬浮的零
- select (6,5) 归零并将 (3,5), (1,5) 添加到暂停的零
现在，剩下的零是 (1,3), (1,4), (3,3), (3,4)
我找不到处理它们的方法，也找不到按列或按行处理的方法。我应该怎么处理它们？
最后是table：
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=selected
- ？ = 我应该做什么
在这个特定的例子中，我们可以任意 select 一个 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
然后我们可以 select 最后的免费 0 并完成。
但这并不总是有效。考虑
0 0 0 0
0 0 0 0
0 0 1 2
0 0 3 4
（如果您更喜欢视频，我使用的是与 here 相同的问题，但我会实际解决它。）
我们不能从头开始select任何东西，所以我们任意select第一个0.
0(se) 0(su) 0(su) 0(su)
0(su) 0 0 0
0(su) 0 1 2
0(su) 0 3 4
现在我们可以 select (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)为0，所以我们可以把(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 个分配，所以这是我们的解决方案。
我正在学习 Youtube of the Indian guy about the Hungarian problem 上的教程。我堆叠在他决定下一步将 select 编辑哪些行和列的位置。他的例子没有我面临的问题。这是我的示例的 table：
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
所以让我们一步步开始行和列selection:
- 第一行包含 >1 个零 => 转到下一行
- select (2,1) 归零并将 (5,1) 添加到悬浮的零
- 第三行包含 >1 个零 => 转到下一行
- select (4,6) 零
- select (5,1) 归零并将 (3,1) 添加到悬浮的零
- select (6,5) 归零并将 (3,5), (1,5) 添加到暂停的零
现在，剩下的零是 (1,3), (1,4), (3,3), (3,4)
我找不到处理它们的方法，也找不到按列或按行处理的方法。我应该怎么处理它们？
最后是table：
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=selected
- ？ = 我应该做什么
在这个特定的例子中，我们可以任意 select 一个 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
然后我们可以 select 最后的免费 0 并完成。
但这并不总是有效。考虑
0 0 0 0
0 0 0 0
0 0 1 2
0 0 3 4
（如果您更喜欢视频，我使用的是与 here 相同的问题，但我会实际解决它。）
我们不能从头开始select任何东西，所以我们任意select第一个0.
0(se) 0(su) 0(su) 0(su)
0(su) 0 0 0
0(su) 0 1 2
0(su) 0 3 4
现在我们可以 select (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)为0，所以我们可以把(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 个分配，所以这是我们的解决方案。