我正在遵循Youtube of the Indian guy about the Hungarian problem上的教程。我的观点是，他决定下一步将选择哪些行和列。他的榜样没有我要面对的问题。这是我的示例表：
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个零=>转到下一行
选择（2,1）零，并将（5,1）加到暂停的零
第三行包含> 1个零=>转到下一行
选择（4,6）零
选择（5,1）零，并将（3,1）加到暂停的零
选择（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 =已选择
？我应该做的事
最佳答案
在这个特定的例子中，我们可以随意选择一个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
（如果您喜欢视频，尽管实际上会解决，但我使用的是与here相同的问题。）
我们从一开始就无法选择任何内容，因此我们可以任意选择前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教授在我链接的视频中介绍了这一过程，因此我将跳过结果。如果画出的线数大于我们要寻找的作业数，则我们继续适当地处理匈牙利算法的其余部分；如果更少，则在上一步中出了点问题，您应该返回并检查工作；但是如果相等（如本例所示），那么我们知道这里有一个尚未找到的最佳解决方案。
我对有问题的任意分配的解决方案是更多的任意分配。第四行是目前唯一没有分配的行，因此我们将从那里开始并分配其前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个作业，所以这是我们的解决方案。
关于java - 匈牙利算法死胡同，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37687045/