我在 C++ 中创建了匈牙利算法的实现。这种实现在许多情况下都非常有效。但是，在某些情况下，我的算法根本不起作用，因为我相信（这是真的）我对算法的一个步骤的实现是错误的。
我的实现将 array 作为输入X，运行算法的步骤并产生最终分配。
该算法的步骤可以在维基上找到：匈牙利算法
在第 3 步中，它具有以下成本数组（工人由行表示，工作由列表示）
然后它说
Initially assign as many tasks as possible then do the following
但是我不明白这将是什么正确的实现。如何分配尽可能多的任务？选择会是随机的吗？然后如果选择是随机的，我可以选择第一个工人做第一份工作，第二个工人做第四份工作，第四个工人做第二份工作。所以第二个工人被排除在外。然而，在维基百科中，作者采取了不同的方法。第三个工人必须做第一份工作，第二个工人必须做第二份工作，第四个工人必须做第二份工作。所以第一个工人被排除在外。
执行此类随机操作的问题是以下情况：
假设当我们运行算法并对输入进行算术运算时，在将尽可能多的任务分配给工作人员之前，我们有以下成本矩阵：
2 2 0 3
6 1 6 0
0 0 6 1
0 3 5 3
如果我随机选择将第三个工作分配给第一个工人，第四个工作分配给第二个工人，然后将第一个工作分配给第三个工人，那么我将遗漏第四个工人。但是为了让算法正常工作，我们需要分配as many jobs to workers as possible. 这是这里的情况吗？不，因为如果不是将第一份工作分配给第三名工人，而是将第一份工作分配给第四名工人，那么我可以将第二份工作分配给第三名工人，因此该算法不仅会为工人分配尽可能多的工作但它会找到最佳结果。
结论：做随机分配不是一个好方法。
我对此进行了一些搜索，发现了以下讲座：
http://www.youtube.com/watch?v=BUGIhEecipE
在本次讲座中，教授提出了一种不同的方法来解决分配尽可能多的任务的问题。根据他的说法，如果任何行或列恰好有一个零，我们将进行分配。因此，从第一行开始，您检查第一行是否只有一个零，如果是这种情况，请进行分配。否则忽略该行并转到第二行，通过重新扫描表重复执行相同的操作，直到由于分配而覆盖所有零。
通过遵循这种方法，可以看到前面的情况得到了解决。我们所做的是，我们将第三个工作分配给第一个工人，第四个工作分配给第二个工人，然后我们看到第三个工人可以做两个工作所以我们暂时忽略他，我们将第一个工作分配给第四个工人然后返回以便将第二份工作分配给第三名工人。
我的实现遵循这个逻辑，但是同样，它并没有解决所有的情况。
让我们以下面的案例为例：
0 0 0 0
0 0 0 0
0 0 4 9
0 0 2 3
第一个工人可以做 4 个工作，第二个 4，第三个 2 和第四个 2。所以我的实现没有分配，因为我需要至少一个只能做一个工作的工人才能完成任务然后继续通过重新扫描表格。那么在这种情况下我该怎么办？随意分配是一件坏事，不幸的是，在那场讲座中没有提出任何建议。我只能想到以下几点：
对于每个工人都有一个计数器，其值表示可以分配给他的任务数量，那么该行中有多少个零？这就是计数器的值。然后开始将任意任务分配给计数器最小的工人。所以在这种情况下，每个工人的计数器数组将包括以下值：
4
4
2
2
例如，我会选择第三名工人并任意分配给他第一份工作。新的计数器将是：
3
3
0
1
然后我会选择第四名工人并为他做唯一的任务（这是第二份工作）。新的计数器将是：
2
2
0
0
然后我可以选择第一个工人或第二个工人。我会为第一个工人做一个任意的任务，然后给他第三个工作。计数器将是
1
0
0
0
最后，我会将第四个任务分配给第一份工作。
所以最后的任务：
0 0 0 *
0 0 * 0
* 0 4 9
0 * 2 3
这似乎是一个很好的方法，但是我担心这种方法可能不起作用的特殊情况。我如何验证这种方法是否适用于所有情况，如果不行，什么方法可以完全解决我的问题？
先感谢您