标签: hungarian-algorithm

我正在尝试实施匈牙利算法,但我坚持第5步.基本上,给定一个n X n数字矩阵,我如何找到最小数量的垂直+水平线,以便覆盖矩阵中的零？

之前有人将这个问题作为一个重复此,该方案中提到有不正确的,别人也跑进贴有代码的bug.

我不是在寻找代码,而是寻找能够绘制这些线条的概念......

编辑:请不要发布简单(但错误)贪心算法:给定此输入:

(0, 1, 0, 1, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 0, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 1, 0)

我明确选择第2列(0索引):

(0, 1, x, 1, 1)
(1, 1, x, 1, 1)
(1, 0, x, 0, 1)
(1, 1, x, 1, 1)
(1, 0, x, 1, 0)

现在我可以选择第2行或第1列,它们都有两个"剩余"零.如果我选择col2,我最终会在这条路径上找到错误的解决方案:

(0, x, x, 1, 1)
(1, x, x, 1, 1)
(1, x, …

我正在尝试用Java实现匈牙利语算法.我有一个NxN成本矩阵.我正在逐步遵循本指南.所以我有costMatrix [N] [N]和2个数组来跟踪被覆盖的行和覆盖的cols - rowCover [N],rowColumn [N](1表示覆盖,0表示未覆盖)

如何用最少的行数覆盖0？谁能指出我正确的方向？

任何帮助/建议将不胜感激.

我有一个分配问题，我想向 SO 社区询问为我的 Spark 数据帧实现此任务的最佳方法（使用 Spark 3.1+）。我将首先描述问题，然后再进行实施。

问题是：我最多有 N 个任务和 N 个个人（在这个问题的情况下，N=10）。每个人执行每项任务都有一定的成本，其中最小成本为 0 美元，最大成本为 10 美元。这是一种匈牙利算法问题，有一些注意事项。

1. 在某些情况下，任务数少于 10 个和/或个人数少于 10 个，并且不向某人分配任务（或不向个人分配任务）是可以的。
2. [更复杂的边缘情况/我遇到麻烦的情况] - 列表中可能有一项任务具有该标志multiTask=True（不能超过 1 个multiTask，也可能没有）。如果一个worker的成本低于x多任务，他会被自动分配给多任务，并且在优化过程中该多任务被认为已被占用。
   • 我将分享几个例子。在此示例中，要分配给多任务的 x 值为 1。
     • 如果 10 名工人中有 1 名在多任务上的成本为 0.25，则他会被分配到多任务，然后其他 9 名工人将被分配到其他 9 个任务
     • 如果 10 名工作人员中的 2 名工作人员在多任务上的成本 < 1，则他们都将被分配到多任务，然后其他 8 名工作人员将被分配到剩余 9 个任务中的 8 个。1 个任务不会分配给任何人。
     • 如果所有 10 个工作人员在多任务上的成本均 < 1，则将所有人员分配给该多任务。这种情况非常罕见，但却是可能的。
     • 如果没有工人在多任务上的成本< 1，则在优化期间多任务将仅分配给一个人，以最小化成本。

这是 Spark 数据框的样子。注意：为了简单起见，我展示了一个示例，其中 N=3（3 个任务，3 个个人）。

from pyspark.sql import Row

rdd …

我在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 …

我正在尝试用C语言实现匈牙利语算法.

我有矩阵:

35  0  0  0
 0 30  0  5
55  5  0 10
 0 45 30 45

而且我要达到我必须找到覆盖所有零的最小线数的阶段(尽可能多地进行分配).显然,通过检查,这是第1列和第3列以及第1行.

维基百科建议采用以下方法:

• 第1行有三个零:选择任何(我选择第一个)并分配它
• 第2行:分配第一个零
• 第3行:分配第3个零
• 第4行未分配(因为唯一的零位于已经指定零的col中)

如果我按照上面的矩阵进行操作,我得到:

35   0'  0   0
 0' 30   0   5
55   5   0' 10
 0  45  30  45

零素数是指定的零.然后,按照下面的维基百科说明,我标记第4行(未分配的零),第1列(带有未分配的零的col),然后是第2行(标记为col的行为零).

所以这意味着命中全零的最小线是:

+--------
|
+--------
|

但这并没有达到零(2, 3).相关C代码:

for (i = 0; i < M->size; i++) {
    for (j = 0; j < M->size; j++) {
        if (M->values[i][j] == 0) {
            if (assigned_cols[j] == 0) { …

所以我有一个工作分配问题,没有匈牙利方法所需的传统成本.

例如:

I have 3 workers - A, B and C
I have 5 jobs -  1, 2, 3, 4 and 5

每个工人都有他可以执行的工作列表,如下所示:

worker A can work on job 1, 2, 5
worker B can work on job 1, 2
worker C can work on job 1

最终结果(因为没有成本)是我可以实现的最大分配数.在这个例子中,我最多可以完成3个任务:

worker A on job 5
worker B on job 2
worker C on job 1

匈牙利方法是解决这个问题的好方法吗？我应该只使用"虚拟"费用吗？我想也许可以使用工作偏好的指数作为成本; 这是一个好主意吗？

匈牙利算法在多项式时间内解决了赋值问题.给定工作人员和任务,以及包含将每个工作人员分配给任务的成本的n×n矩阵,它可以找到最小化成本的分配.

我想找到最大成本的选择？我可以使用匈牙利语或任何类似的方法吗？或者这只能以指数方式完成？

假设我们有N个工作岗位和K工人做这些工作.但对于一些工作,我们需要2名员工,而对于一些人,我们只需要一名.员工也无法完成所有工作.例如,工人1可以做工作1,2和5,而不是工作3和4.此外,如果我们雇佣工人1来做工作1,那么我们希望他做第2和第5工作,因为我们已经付了工资.

例如,假设我们有5个工作岗位和6个工人.对于1,2和4工作,我们需要2个人,而对于工作3和5,我们只需要一个.这里是每个工人可以做的工作清单和他需要的工资.

Worker 1 can do jobs 1,3,5 and he requires 1000 dollars. 
Worker 2 can do jobs 1,5 and he requires 2000 dollars. 
Worker 3 can do jobs 1,2 and he requires 1500 dollars. 
Worker 4 can do jobs 2,4 and he requires 2500 dollars. 
Worker 5 can do jobs 4,5 and he requires 1500 dollars. 
Worker 6 can do jobs 3,5 and he requires 1000 dollars. 

经过一些计算和逻辑思考,我们可以得出结论,我们必须雇用1,3,4和5工人,这意味着我们需要支付的最低工资是:1000 + 1500 + 2500 + 1500 = 5500美元.

但是我们如何才能找到一个可以输出该数量的高效算法呢？这让我想起了匈牙利算法,但所有这些额外的约束使我无法应用它.

我正在尝试实现匈牙利算法。除了矩阵不是方形的时候，一切都很好。我搜索过的所有方法都说我应该通过添加虚拟行/列并用矩阵中的最大数字填充虚拟行/列来使其成为正方形。我的问题是这不会影响最终结果吗？虚拟行/列不应该至少填充max+1 吗？

我有一个问题困扰我一段时间了.

我们有"工人"w_0,w_1 ... w_n,以及任务t_0,t_1,... t_m和持续时间D_ij,使得w_i可以在该小时数内完成t_j.每个工作人员还可以使用最多m_0,m_1 ... m_n小时数.

多个工作人员可以通过按比例分配的工作来完成相同的任务.例如,如果D_11 = 2且D_21 = 4,则工作人员1在任务1上的效率是工人2的两倍.因此,您可以组合,例如1小时1的工作和2的2工作以完成任务.

我们如何确定完成所有任务的最短小时数.

我已经尝试使用贪婪技术为每个任务选择最佳工作者,但这并不适用于每个案例.例如,工人1可以在2小时内完成任务1,在4小时内完成任务3.很明显,工人1将被选中从事任务1工作,尽管如此,让我们说任务3对于其他工人来说非常耗时,而工人1对于工作来说是完美的.

我已经考虑过将问题减少到一个任务问题,但没有找到方法的运气.

怎样才能解决这个问题？