问题标签 [hungarian-algorithm]

我正在尝试找到一种算法来将“参与者”分配给一组组中的一个。对于每个参与者，都有他们对组的偏好排名。我需要一种算法以尽可能最好的方式将所有参与者分配到组中。经过一些研究，似乎我正在寻找的是匈牙利算法的一个版本，但如果存在不等集的话。我也读了很多关于稳定婚姻问题和 Gale-Shapely 算法的书，但我不知道这是否适用，因为这些团体不会有参与者的偏好。谢谢！

I need to develop a polynomial-time algorithm for this problem but I'm a little confused. I need to minimize the maximum cost among the assignments, not the total cost of all assignments. I tried using the Hungarian method but it finds the minimum total cost, not minimum of the maximum value.

How should I go about it?

我有一个大的 2D成本矩阵：500K x 500K，我想解决分配问题。除了匈牙利算法，我想使用下面的贪心算法来减少时间：

使用一个内核将需要很长时间（对于 5Kx5K，单线程需要 40 分钟）。我想我们不能并行化嵌套循环，因为我们需要最好的变量。正确的？我尝试将此代码并行化，但它给了我许多重复的列。

有什么建议可以更快地运行贪心算法（我的并行解决方案不起作用）？

我正在尝试在我的项目中实现匈牙利算法，但我不明白为什么它会产生无限循环......我尝试过使用其他 bibartite 图并且它有效。所以我想知道我的图表有什么问题G

我正在尝试实施匈牙利算法。检查维基百科的步骤：https ://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation

考虑以下输入 (10 x 10)：

它需要 8 行来覆盖所有零（从 0 开始索引的行和列）：R0 R1 R2 R5 C0 C5 C8 C9。

但是，请遵循维基百科中给出的步骤：

1. 将零标记为“已分配”或“划掉”。已分配：(0, 2)，划掉：(0, 4) (0, 6) (1, 2)；已分配：(2, 0)，划掉：(2, 1) (2, 7) (6, 0)；已分配：(3, 5)，划掉：(4, 5)；已分配：(5, 3)，划掉：(5, 4)；已分配：(7, 8)，划掉：(7, 9) (9, 8)；已分配：(8, 9)。
2. 标记所有没有分配的行：R1 R4 R6 R9；在新标记的行中标记所有具有零的列：C2 C5 C0 C8；在新标记的列中标记所有具有分配的行：R0 R3 R2 R7。
3. 重复2中的最后两步，直到没有行或列可以被标记：在新标记的行中标记所有具有零的列：R0->C4 C6，R3->none，R2->C1 C7，R7->C9；在新标记的列中标记所有具有分配的行：C4 C6 C1 C7->none，C9->R8。

现在除了 R5 之外的所有行都被标记了；除 C3 外的所有列均已标记。覆盖所有零所需的行数将是 9 垂直 + 1 水平 = 10，这是不正确的。

谁能告诉我在哪里犯了错误？或者获得最小线的算法本身是不完美的？

我目前正在编写一个算法来通过兼容性分数匹配用户。因此，每个用户与其他每个用户都有一个兼容性分数。目标是最大化总兼容性分数。我正在使用munkres python 包来获取索引，然后过滤重复项。（即如果 user1 与 user2 匹配，我们删除与 user2 和 user1 的匹配）。

这是一个示例矩阵：（在用户无法与自己匹配的地方禁止使用。）

这是我尝试过的。它适用于我给出的这个较小的矩阵示例，但没有给出较大数据集的最佳分数。我知道总分不是最优的，因为非优化算法（简单地对分数进行排序并按顺序匹配每个用户）会产生更高的分数。

是否有某个矩阵会破坏我的代码？任何帮助或指示将不胜感激。

除了求解大小为 n*m 的矩阵外，是否有与匈牙利方法类似的算法？

（n - 工人，m - 任务，m > n，每个工人必须至少有 1 个任务）

添加虚拟工作者的变体是不正确的，因为在这种情况下，至少有 1 个任务将没有工作者。

例子：

结果是：

W1 - T2

W2 - T4

W3 - T1, T3

根据我在此链接中阅读的文章，在某些条件下，分配问题可以变成最大流问题。我知道最小成本流问题的转换，但是我想知道从这个方法中，这个问题在什么条件下变成最大流问题？

这更多的是成本估算问题，而不是如何使用节点亲和性等特性。

所以基本上有m一些限制，比如：

• 每个特定Deployments/的 podStatefulSets应该在不同的 kubernetes 节点上
• Deployments特定/的 podStatefulSets应在 3 个可用区上进行平衡

现在，我想找出我需要多少个节点（所有相同类型）来托管给定的Deployments/集StatefulSets。

我最初认为这更像是一个使用匈牙利算法解决的分配问题，但这在术语上似乎要复杂得多，比如多维约束。

问题设置

目前，我们正在为一家食品科技初创公司（电子杂货店）解决配送问题。我们有工作（要交付的订单）和工人（快递员/包装员/通用）问题是如何有效地将订单分配给工人。第一步，我们决定优化 CTE（点击即食 - 下订单和订单交付之间的时间）

问题本身

问题来自这样一个事实，即有时每个作业有 2 个工人而不是单个执行者是有效的，因为打包者可能知道商店“地图”，而快递员可能有自行车，与他们中的每一个相比，它们可以更快地执行作业，甚至计算订单转移成本。

我们研究了算法，发现我们的问题看起来像分配问题，并且有一个算法解决方案（匈牙利算法），但问题是经典问题要求“每个工作分配给一个工人，每个工人分配一份工作”，而在在我们的案例中，有时每份工作有 2 个工人是有效的。

到目前为止我们所做的尝试

1. 将（打包机 A +通用 B）组合插入成本矩阵，但在这种情况下，我们不能将 通用 B添加到矩阵中，因为结果我们可以得到通用 B将分配给 2 个工作（作为一个单独的单元和作为与封隔器 A组合的一部分）

2. 因此实施 2 种匈牙利算法：首先分配包装，然后分配交付。它在绝大多数情况下都有效，但有时会导致效率低下的解决方案。如果需要，我将添加一个示例。

问题本身

我用谷歌搜索了很多，但找不到任何可以指导我解决问题的方法。如果您有任何链接或想法可以用作解决方案的线索，我将很乐意检查它们。

编辑：我已经添加了我的问题的蛮力解决方案。希望这有助于更好地理解问题