问题标签 [hungarian-algorithm]

我正在尝试对匈牙利算法进行体面的实现，但是我被困在如何找到覆盖数组中所有零的最小行数

我还需要知道这些行以便稍后进行一些计算

这是解释：

http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf

在第 3 步中它说

使用尽可能少的行来覆盖矩阵中的所有零。没有简单的规则可以做到这一点 - 基本上是反复试验。

试错在计算方面意味着什么？例如，如果我有一个 5 行 5 列的二维数组，那么

第一行可以覆盖所有的零，第一和第二，第一行和第一列等等太多的组合

没有比这更有效的吗？

提前致谢

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

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

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

我正在尝试用 Java 实现匈牙利算法。我有一个 NxN 成本矩阵。我正在逐步遵循本指南并已达到第 9 步 -

“通过选择一组零来选择匹配项，以便每一行或每一列都只选择一个。”

我已经有了带有 0 的矩阵。我试图弄清楚这一点，唯一对我有用的是蛮力方法。

我还想过选择我遇到的第一个 0，删除该列和行并重复；但是这种方法行不通。

有什么诀窍或方法吗？不是太复杂的东西？任何建议将不胜感激。

谢谢

我在 C++ 中创建了匈牙利算法的实现。这种实现在许多情况下都非常有效。但是，在某些情况下，我的算法根本不起作用，因为我相信（这是真的）我对算法的一个步骤的实现是错误的。

我的实现将 array 作为输入X，运行算法的步骤并产生最终分配。

该算法的步骤可以在维基上找到：匈牙利算法

在第 3 步中，它具有以下成本数组（工人由行表示，工作由列表示）

然后它说

但是我不明白这将是什么正确的实现。如何分配尽可能多的任务？选择会是随机的吗？然后如果选择是随机的，我可以选择第一个工人做第一份工作，第二个工人做第四份工作，第四个工人做第二份工作。所以第二个工人被排除在外。然而，在维基百科中，作者采取了不同的方法。第三个工人必须做第一份工作，第二个工人必须做第二份工作，第四个工人必须做第二份工作。所以第一个工人被排除在外。

执行此类随机操作的问题是以下情况：

假设当我们运行算法并对输入进行算术运算时，在将尽可能多的任务分配给工作人员之前，我们有以下成本矩阵：

如果我随机选择将第三个工作分配给第一个工人，第四个工作分配给第二个工人，然后将第一个工作分配给第三个工人，那么我将遗漏第四个工人。但是为了让算法正常工作，我们需要分配as many jobs to workers as possible. 这是这里的情况吗？不，因为如果不是将第一份工作分配给第三名工人，而是将第一份工作分配给第四名工人，那么我可以将第二份工作分配给第三名工人，因此该算法不仅会为工人分配尽可能多的工作但它会找到最佳结果。

结论：做随机分配不是一个好方法。

我对此进行了一些搜索，发现了以下讲座：

http://www.youtube.com/watch?v=BUGIhEecipE

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

通过遵循这种方法，可以看到前面的情况得到了解决。我们所做的是，我们将第三个工作分配给第一个工人，第四个工作分配给第二个工人，然后我们看到第三个工人可以做两个工作所以我们暂时忽略他，我们将第一个工作分配给第四个工人然后返回以便将第二份工作分配给第三名工人。

我的实现遵循这个逻辑，但是同样，它并没有解决所有的情况。

让我们以下面的案例为例：

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

对于每个工人都有一个计数器，其值表示可以分配给他的任务数量，那么该行中有多少个零？这就是计数器的值。然后开始将任意任务分配给计数器最小的工人。所以在这种情况下，每个工人的计数器数组将包括以下值：

例如，我会选择第三名工人并任意分配给他第一份工作。新的计数器将是：

然后我会选择第四名工人并为他做唯一的任务（这是第二份工作）。新的计数器将是：

然后我可以选择第一个工人或第二个工人。我会为第一个工人做一个任意的任务，然后给他第三个工作。计数器将是

最后，我会将第四个任务分配给第一份工作。

所以最后的任务：

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

先感谢您

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

例如：

每个工人都有一个他可以执行的工作列表，如下所示：

最终结果（因为没有成本）是我可以完成的最大任务数。在这个例子中，我最多可以完成 3 个作业：

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

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

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

我正在尝试按照匈牙利方法中用最少行数覆盖零的步骤，如下所示：

1. 勾选所有未分配的行。
2. 如果勾选的行为零，则勾选对应的列。
3. 在勾选的列中，如果有分配，则勾选对应的行。
4. 在每个未勾选的行和勾选的列上方画一条线。
5. 对每个未分配的行重复此操作。
6. 然后找到 Theta（这是最小的未覆盖值）

问题是当我这样做时，我仍然发现零！导致 Theta 为零并进入无限循环！

例如，如果我们采用以下矩阵 25 x 25)：

1 5 5 2 3 1 2 3 2 4 5 2 3 1 5 5 2 3 1 5 1 4 3 2 5

5 5 3 2 3 2 5 1 4 3 2 5 3 2 4 5 2 5 2 1 1 4 1 2 5

5 1 4 3 2 5 1 1 4 1 2 5 2 2 3 4 1 4 5 3 2 4 5 2 5

1 1 4 1 2 5 3 2 4 5 2 5 5 5 1 5 1 5 5 2 2 3 4 1 4

3 2 4 5 2 5 2 2 3 4 1 4 5 4 2 1 3 2 5 5 5 1 5 1 5

2 2 3 4 1 4 5 5 1 5 1 5 5 5 2 5 5 1 4 5 4 2 1 3 2

5 5 1 5 1 5 5 5 3 2 3 2 1 5 5 1 5 1 5 5 5 2 5 5 1

5 4 2 1 3 2 5 1 4 3 2 5 5 5 4 2 1 3 2 5 1 4 3 2 5

5 5 2 5 5 1 1 1 4 1 2 5 1 5 5 2 5 5 1 1 1 4 1 2 5

2 4 5 3 4 2 3 2 4 5 2 5 2 2 4 5 3 4 2 3 2 4 5 2 5

2 2 5 5 1 3 2 2 3 4 1 4 2 2 2 5 5 1 3 2 2 3 4 1 4

4 1 5 4 5 3 5 5 1 5 1 5 5 4 1 5 4 5 3 5 5 1 5 1 5

5 1 4 3 2 5 3 2 4 5 2 5 5 5 1 4 3 2 5 3 2 4 5 2 5

1 1 4 1 2 5 2 2 3 4 1 4 1 1 1 4 1 2 5 2 2 3 4 1 4

3 2 4 5 2 5 5 5 1 5 1 5 4 3 2 4 5 2 5 5 5 1 5 1 5

2 2 3 4 1 4 5 4 2 1 3 2 1 2 2 3 4 1 4 5 4 2 1 3 2

5 5 1 5 1 5 5 5 2 5 5 1 2 5 5 1 5 1 5 5 5 2 5 5 1

5 1 4 3 2 5 3 5 1 4 3 2 5 3 5 2 2 3 5 2 2 3 2 5 3

3 4 1 4 1 1 1 1 1 4 1 2 5 5 1 4 3 2 5 1 4 1 2 5 2

1 5 5 2 3 1 5 3 2 4 5 2 5 1 1 4 1 2 5 2 4 5 2 5 5

5 5 3 2 3 2 2 2 2 3 4 1 4 3 2 4 5 2 5 2 3 4 1 4 3

5 1 4 3 2 5 2 5 5 1 5 1 5 2 2 3 4 1 4 5 1 5 1 5 5

1 1 4 1 2 5 2 5 4 2 1 3 2 5 5 1 5 1 5 4 2 1 3 2 1

3 2 4 5 2 5 1 5 5 2 5 5 1 5 4 2 1 3 2 5 2 5 5 1 3

2 2 3 4 1 4 1 2 4 5 3 4 2 5 5 2 5 5 1 4 5 3 4 2 2

从匈牙利方法中减去最小行和列值作为步骤 1 和 2 后，我得到：

0 4 4 1 2 0 1 2 1 3 4 1 2 0 4 4 1 2 0 4 0 3 2 1 4

4 4 2 1 2 1 4 0 3 2 1 4 2 1 3 4 1 4 1 0 0 3 0 1 4

4 0 3 2 1 4 0 0 3 0 1 4 1 1 2 3 0 3 4 2 1 3 4 1 4

0 0 3 0 1 4 2 1 3 4 1 4 4 4 0 4 0 4 4 1 1 2 3 0 3

2 1 3 4 1 4 1 1 2 3 0 3 4 3 1 0 2 1 4 4 4 0 4 0 4

1 1 2 3 0 3 4 4 0 4 0 4 4 4 1 4 4 0 3 4 3 1 0 2 1

4 4 0 4 0 4 4 4 2 1 2 1 0 4 4 0 4 0 4 4 4 1 4 4 0

4 3 1 0 2 1 4 0 3 2 1 4 4 4 3 1 0 2 1 4 0 3 2 1 4

4 4 1 4 4 0 0 0 3 0 1 4 0 4 4 1 4 4 0 0 0 3 0 1 4

0 2 3 1 2 0 1 0 2 3 0 3 0 0 2 3 1 2 0 1 0 2 3 0 3

1 1 4 4 0 2 1 1 2 3 0 3 1 1 1 4 4 0 2 1 1 2 3 0 3

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

4 0 3 2 1 4 2 1 3 4 1 4 4 4 0 3 2 1 4 2 1 3 4 1 4

0 0 3 0 1 4 1 1 2 3 0 3 0 0 0 3 0 1 4 1 1 2 3 0 3

2 1 3 4 1 4 4 4 0 4 0 4 3 2 1 3 4 1 4 4 4 0 4 0 4

1 1 2 3 0 3 4 3 1 0 2 1 0 1 1 2 3 0 3 4 3 1 0 2 1

4 4 0 4 0 4 4 4 1 4 4 0 1 4 4 0 4 0 4 4 4 1 4 4 0

4 0 3 2 1 4 2 4 0 3 2 1 4 2 4 1 1 2 4 1 1 2 1 4 2

2 3 0 3 0 0 0 0 0 3 0 1 4 4 0 3 2 1 4 0 3 0 1 4 1

0 4 4 1 2 0 4 2 1 3 4 1 4 0 0 3 0 1 4 1 3 4 1 4 4

4 4 2 1 2 1 1 1 1 2 3 0 3 2 1 3 4 1 4 1 2 3 0 3 2

4 0 3 2 1 4 1 4 4 0 4 0 4 1 1 2 3 0 3 4 0 4 0 4 4

0 0 3 0 1 4 1 4 3 1 0 2 1 4 4 0 4 0 4 3 1 0 2 1 0

2 1 3 4 1 4 0 4 4 1 4 4 0 4 3 1 0 2 1 4 1 4 4 0 2

1 1 2 3 0 3 0 1 3 4 2 3 1 4 4 1 4 4 0 3 4 2 3 1 1

然后当我们进行赋值时，我们将有 23 个赋值而不是 25 个，所以我们根据上述步骤进行前面提到的覆盖零，我会得到以下结果：

粗体单元格是根据上述步骤覆盖的单元格。

请注意，仍然有未发现的零导致无限循环，因为它将在接下来被选中。

请帮我。

先感谢您

我在 2D 中有一组偶数点。我需要一种算法，可以使这些点成对，使成对之间的距离总和最大。

我认为，动态编程，贪婪的方法是行不通的。我可以使用线性规划或匈牙利算法吗？或任何其他？

我正在研究分配问题的变体。以前，我使用匈牙利算法来确定最适合早班的作业。它考虑了员工是否接受过培训，以及他们最近在该职位上完成理想任务的时间。

问题是我需要制作另一个程序来执行“旋转”。也就是根据白班的分配给我们的夜班分配。如果我们的员工在双班工作，我们希望确保他们在夜班时处于不同的位置。此外，如果有人在白班工作，我们喜欢在晚上让某人上夜班来填补他们的位置，以便于更换两名员工。

我觉得这可以通过最小流问题的一些变化来实现，但我很好奇是否有人知道一种算法或策略来最好地解决通过轮换创建夜间分配的问题。

为了澄清我所说的轮换的意思，假设有四个职位：收银员、装袋员、迎宾员和轮班领导。对于早班，Abe 是收银员，Ben 是 Bagger，Cathy 是迎宾员，Dale 是班长。除了只上早班的戴尔之外，所有人都在打双打。

晚上，Edward 是唯一进来的员工，因此他将取代唯一的白班 (Dale) 作为班长（当然假设他知道那个职位）。

这使得 Abe、Ben 和 Cathy 需要轮换。假设他们知道这些职位，这可能是简单的事情，比如 Ben 被转移到 Cashier，Cathy 被转移到 Bagger，Abe 被转移到 Greeter。

这当然只是一个例子。培训和其他因素出现。生成培训是完全可以的，但理想情况下，这将是可能的最低限度。

目前我有一个n用户数量的数据库。所有这些用户都有一个与其他用户相关的分数，比如兼容性分数。这些分数是对称的。因此，如果 user1 与 user2 的得分为 10，则 user2 与 user1 的得分为 10，依此类推。

我正在寻找一种方法来匹配所有用户，同时最大化所有用户的总分。

这显然被称为匈牙利算法？虽然寻找最高分而不是最低分。

有没有一种干净的方法是Rails？我到处寻找，却找不到任何东西。