我已经在C++中创建了匈牙利算法的实现。这种实施非常适用于很多的情况。但是，有些情况下我的算法根本无法工作，因为我相信（而且的确如此），我的算法的一步执行是错误的。匈牙利算法：我尽可能多地为工作人员分配工作
我的实现需要输入数组X，运行算法的步骤并产生最终的分配。
的算法的步骤可以在wiki上找到：Hungarian Algorithm
在步骤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
在本次讲座教授建议分配尽可能多的任务尽可能的问题，不同的方法。 据他说，如果任何行或列只有一个零，我们会做一个任务。因此，从第一行开始，检查第一行 是否只有一个零，如果是这种情况，请进行分配。否则，忽略该行并转到第二行，通过重新扫描表重复执行相同的操作，直到归因于赋值而覆盖所有的零。
通过遵循这种方法，可以看到前一个案例已解决。我们所做的是，我们将第三份工作分配给第一名工人，第四份工作分配给第二名工人，然后我们看到第三名工人可以拿到2份工作，所以我们暂时忽略他，我们将第一份工作分配到第四份工作然后返回，以便将第二份工作分配给第三名工人。
我的实现遵循这个逻辑，但是，它并没有解决所有的情况。
让我们例如下面的情况：
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
这似乎是一个好办法，但恐怕有可能是一个特殊的情况下，这种方法是行不通的。我如何验证这种方法是否适用于所有情况，如果不能，那么采用什么方法可以完全解决我的问题？
预先感谢您
匈牙利算法？工人？没有办法... [/自嘲的讽刺] – 2013-03-09 19:51:48
我喜欢你目前的做法 - “我相信（这是真的）”。 – SChepurin 2013-03-09 20:07:17
@ H2CO3，我计划发布“你确定它不是希腊算法吗？”但你应该在这里拥有整个房间;） – Sebas 2013-03-09 22:30:48