匈牙利算法:我在为工人分配尽可能多的工作时遇到了麻烦

Question

我在C++中创建了匈牙利算法的实现.对于许多情况,此实现非常有效.然而,在某些情况下,我的算法根本不起作用,因为我相信(而且这是真的)我执行算法的一步是错误的.

我的实现将数组作为输入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

在这个讲座中,教授为分配尽可能多的任务的问题提出了一种不同的方法.根据他的说法,如果任何行或列只有一个零,我们将进行一项任务.因此,从第一行开始,检查第一行是否只有一个零,如果是这种情况,请进行分配.否则忽略该行并转到第二行,通过重新扫描表重复执行相同的操作,直到由于赋值而覆盖了所有零.

通过遵循这种方法,可以看出先前的案例已经解决.我们做的是,我们将第三个工作分配给第一个工人,第四个工作分配给第二个工人,然后我们看到第三个工人可以从事2个工作因此我们暂时忽略他,我们将第一个工作分配到第四个工作工人然后返回,以便将第二个工作分配给第三个工人.

我的实现遵循这个逻辑,但是,它并没有解决所有情况.

我们以下面的例子为例:

0 0 0 0
0 0 0 0
0 0 4 9
0 0 2 3

第一个工人可以完成4个工作,第二个工作4个,第三个工作2个工作和第四个工作2个.所以我的实施没有任务,因为我需要至少一个工人只能从事一项工作才能完成任务然后继续通过重新扫描表格.那么在这种情况下我该怎么办？任意作业将是一件坏事,不幸的是,在那个讲座中没有提出任何建议.我只能想到以下几点:

对于每个工人都有一个计数器,其值表示可以分配给他的任务数量,那么我们在该行中有多少个零？这是柜台的价值.然后开始使用最小的计数器将任意任务分配给工作人员.因此,在这种情况下,每个worker的计数器数组将包含以下值:

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

这似乎是一个很好的方法,但我担心可能会有一个特殊情况,这种方法不起作用.如何验证这种方法是否适用于所有情况,如果不适用,哪种方法可以完全解决我的问题？

先感谢您

Answer 1

您当前的方法不起作用。

0 2 0
3 0 0
4 0 0

你的方法：“然后开始将任意任务分配给具有最小计数器的工人。”所有工人都有相同的计数器，所以假设你选择工人1并将他分配给任务3，你只能匹配剩余工人之一，而这个矩阵显然可以匹配所有三个。

您需要的是这些工作人员和任务之间的最大二分匹配，其中如果相关位置中有 0，则一对是可匹配的。这种匹配可以通过手动遍历增广路径来找到，或者使用 Hopcroft-Karp 算法更快地找到。