问题标签 [hungarian-algorithm]

在特定情况下，我需要帮助解决分配问题。在一种情况下，利润矩阵维度为 2000 乘以 23000（2000 个项目和 23000 个箱，其中每个箱只能包含一个项目，并且没有负利润）。如果应用匈牙利赋值，该算法将首先创建一个 23000 乘 23000 的方阵，并导致 OutOfMemory 异常。

我要解决的问题正是最优分配方案所能产生的最大利润。因此不需要输出实际的最优分配，只需要最优值。这个值也可以只是一个近似值。我想知道是否存在可以节省内存和计算成本的替代方法。

提前致谢。

我目前正在尝试了解有关旅行商问题 (TSP) 的更多信息。我从互联网上找到了一些关于解决这个问题的启发式算法，例如蚁群优化、lin-kernighan、pairwise exchange 等。

另一方面，还有其他算法，如help-karp和分支定界算法。

他们提到他们解决了 TSP，但他们似乎正在通过中间的任何点找到从 A 点到 G 点的最短路径，这可以缩短路径。

在这种情况下，我认为它们与 Dijiktra 算法非常相似......

最重要的是，其中一些算法正在使用权重进行计算。他们通常使用的重量是多少？是距离吗？他们如何实际获得所有这些信息？

据我了解，TSP 是需要前往几个指定的地点，然后往返于同一个起点，不是吗？

诸如匈牙利算法之类的算法似乎更恰当地回答了 TSP，不是吗？

但是，我找不到太多关于这个算法的研究论文。

请指教。

我正在尝试在 C 中实现匈牙利算法。

我有矩阵：

我已经到了必须找到覆盖所有零的最少行数的阶段（尽可能多地分配）。显然，通过检查，这是第 1 列和第 3 列以及第 1 行。

维基百科建议以下方法：

• 第 1 行有三个零：选择任何一个（我选择第一个）并分配它
• 第 2 行：分配第一个零
• 第 3 行：分配第三个零
• 第 4 行未分配（因为唯一的零在一个已经分配了零的列中）

如果我在上面的矩阵中遵循这个，我得到：

其中零素数是分配的零。然后，按照下面维基百科的说明，我标记第 4 行（未分配的零）、第 1 列（未分配零的列），然后是第 2 行（标记的列中的零行）。

因此，这表明达到全零的最小行是：

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

此代码选择哪些零是零素数（分配零）。

然后此代码标记在新标记的列中具有分配的所有行：

但这（和维基百科的解释）对于我上面的矩阵失败了。怎么来的？

我希望将匈牙利算法C应用于由列表的叉积索引的 numpy 矩阵的许多子集row_ind，col_ind. 目前，我看到了以下选项：

1. 双切片：

   /li>

问题：每个子集操作有两个副本。

2. 高级切片通过np.ix_：

   /li>

问题：每个子集一个副本，np.ix_效率低下（分配nxn矩阵）。

更新：正如@hpaulj 所指出的，np.ix_它实际上不是分配了 nxn 矩阵，但它仍然比 1 慢。

3. 蒙面数组。

问题：不适用于linear_sum_assignment.

所以，没有一个选项是令人满意的。

理想情况下，需要能够使用矩阵C和一对分别用于行和列的一维掩码来指定子矩阵视图，因此可以将这样的视图传递给linear_sum_assignment. 对于另一个linear_sum_assignment电话，我会快速调整掩码，但从不修改或复制/子集整个矩阵。

numpy中是否已经有类似的东西可用？

处理同一大矩阵的多个子矩阵的最有效方法是什么（尽可能少的副本/内存分配）？

是否有匈牙利算法的扩展来满足每个工人分配多个工作的需求？在最简单的形式中，该算法将单个工作分配给单个工人。

我的应用程序是一个利润最大化问题，有 3 个工人和 180 个工作岗位。我还将添加约束（至少为每个工人分配 50 个工作）。

我已经设法使用 Python 中的 mungres 库实现了匈牙利算法，效果很好。我只是在努力寻找与每个工人的多项任务相关的文献。

https://pypi.python.org/pypi/munkres

https://en.wikipedia.org/wiki/Hungarian_algorithm

https://en.wikipedia.org/wiki/Generalized_assignment_problem

我已经尝试了评论中列出的标准 numpy 方法，但无法将其扩展到每个工作人员的多个任务。如果我的矩阵是矩形的（即 3 个工人和 4 个工作），则只有前 3 个工作分配给工人。我还尝试添加虚拟变量来创建方阵，但随后将工作分配给那些虚拟工人而不是实际工人

我一直在尝试实现 0(n^3) 版本的匈牙利算法。我遇到了 munkres 库，因为他们声称运行时间为 0(n^3)。通过查看他们的代码，我不确定他们如何测量 0(n^3)，因为它看起来像 0(n^4)。

这些是我正在查看的函数，我认为要找到零函数，复杂度为 0(n^2)，并且由于它在 step4 的 while 循环中被调用，因此复杂度为 0(n^3)。步骤 4 在计算中的 while 循环中调用，使复杂度为 0(n^4)。我想知道他们如何声称拥有 0(n^3)？

I'm trying to re-write a python algorithm to Java for some needs.

In python algorithm I have the following code :

linear_sum_assignment is a scipy function

Do you guys know an equivalent of that function in java ? I found this one but I didn't get the row indice and column indice in this one.

这是场景：

B1、B2、B3、B4、B5、B6 是块

S1、S2、S3 是插槽

每个块都可以放入特定的插槽中。

即， B1 = ["S1","S2", "S3"] 。可以将装置 B1 放入这 3 个插槽中。

B2 = [S1，S2]

B3 = [S3]

您可以通过从每个插槽中取出一个块来制作产品 -

即，产品的配方是（来自 S1 的 1）+（来自 S2 的 1）+（来自 S3 的 1）

需要一个函数/算法将这些块放在每个插槽中以制造最大数量的产品。

在给定的示例中 - B3 将在 S3 中，因为 B3 只允许放入该插槽中。但是，虽然 B1 可以放在任意 3 个插槽中，但我们应该放在 S1 中，因为要制作设备，我们需要 S1 + S2 + S3 并且 B3 只能放在 S3 中。所以在插槽之间分配块的最佳方式是：B1-> S1, B2 -> S2, B3 -> S3

所以我们可以按照配方制作一种产品，即（1 来自 S1 + 1 来自 S2 +1 来自 S3 ）

我尝试了以下代码：

它给出了这个输出

{'B4'：'S1'，'B5'：'S3'，'B6'：'S1'，'B7'：'S1'，'B1'：'S1'，'B2'：'S1'，' B3'：'S1'，'B8'：'S1'，'B9'：'S3'}

有了这个，我们无法制造任何产品，因为 S2 中没有块。

尝试了另一种更好但仍不完美的解决方案。下面是代码。它给出了这个输出：

{'B4'：'S1'，'B5'：'S3'，'B6'：'S2'，'B7'：'S1'，'B1'：'S3'，'B2'：'S1'，' B3'：'S2'，'B8'：'S3'，'B9'：'S2'}

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

我在我的项目中使用 muncres3（它实现了匈牙利算法）我需要将一些字段标记为 DISALLOWED，因为我在 muncres 中能够做到这一点。请问有谁在muncres3中实现了这个功能？

谢谢