0

我有一个正常的分配问题，我想将工人与工作相匹配。但是有几种工作，每种都有一定数量的职位。因此，例如，我需要 10,000 名建筑工人、5,000 名焊工等。当然，每个工人对同一种工作的每个职位都有相同的偏好。

我目前的方法是使用匈牙利算法并扩展矩阵列来解决这个问题。因此，例如，它将有 10,000 个构建器柱、5,000 个焊工等。当然，对于 O(n 3 ) 和这么大的矩阵，获得结果可能需要一段时间。

匈牙利算法是否有任何变体，或者不同的算法，它使用了一个事实，即可以有多个连接到一个作业节点？还是应该研究蒙特卡洛或遗传搜索树算法？

编辑：

Sascha 提出的正式描述：

为工人设置 W，为工作设置 J，公式为偏好设置权重函数，公式为可用工作数量设置函数

所以我想最小化的功能是：公式

在哪里公式

约束将是：

公式

和

公式

正如 Yay295 所问的，如果它在普通消费者机器上运行一两天就可以了。现在有 50k 工人，有 10 种工作，总共 50k 个工作。因此，在我现在使用的匈牙利算法的情况下，矩阵是 50k x 50k（扩展），对于带有附加约束的 LP，矩阵是 50k x 10 公式，而公式矩阵中的偏好值将从 0-100 变化。

4

1 回答 1

1

这实际上被称为运输问题。运输问题与分配问题相似，它们都有来源和目的地，但运输问题还有两个值：每个来源都有供应，每个目的地都有需求。分配问题是运输问题的简化，其中每个来源的供应和每个目的地的需求为 1。

在您的情况下，您有 50,000 个来源（您的工人），每个来源都有 1 个（每个工人只能从事一份工作）。您还有 10 个目的地（工作类型），每个目的地都有一定的需求量（该类型的职位空缺数量）。

运输问题传统上是用单纯形算法解决的。我无法告诉你它是如何运作的，但是网上其他地方有很多关于如何做到这一点的信息。我会推荐这两个视频：第一，第二。

 

或者，运输问题实际上也可以使用匈牙利算法来解决。这个想法是分别跟踪您的供需，然后使用匈牙利算法（或任何其他分配问题的算法）来解决它，就好像供需为 1（当它不平衡时，这可能会非常快50,000 个来源到 10 个目的地，就像你的情况一样）。解决一次后，使用结果适当地减少分配的解决方案的供应和需求。重复直到供给或需求的总和为零。

然而，这些都不是必需的。几年前，我用 C++ 编写了自己的分配问题求解器，尽管使用了 2.5GB 的 RAM，但它可以在不到 5 秒的时间内解决 50,000 x 50,000 的分配问题。诀窍是自己编写。在我写我的之前，我看了看网上有什么，它们都很糟糕，经常有明显的错误。但是，如果您要为此编写自己的代码，最好使用我上面链接的视频中描述的 Simplex 算法。我不知道一个比另一个快，但匈牙利算法不是为运输问题而设计的。

 

ps：我上面链接的两个讲座的同一个人也做了一个关于作业问题和匈牙利算法的讲座。

于 2016-06-05T20:24:45.133 回答