algorithm - 具有大且不平衡的利润矩阵的匈牙利分配方案

Question

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

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

提前致谢。

Answer 1

您实际上可以只用一列模拟所有虚拟列。

我不知道您要遵循哪些具体指令，但算法中的步骤之一是使用尽可能少的水平和垂直线来覆盖矩阵中的每个零。在所有虚拟列仍然为零时，覆盖它们的最有效方法是按列覆盖它们。某些行也可能被覆盖，并且被覆盖两次的值会增加一个数量。更重要的是，每个虚拟列中的同一行将增加相同的数量。

现在继续，虚拟列的某些行不为零，我们再次到达这一步。由于所有虚拟列仍然相同，因此如果覆盖一个虚拟列是有效的，则它们都将被覆盖。因此，即使值可能会发生变化，每个 dummy column 将始终与其他每个 dummy column 相同，因此您可以仅使用一个数组来表示它们。

如果您有大量真实数据，您可能仍然会遇到问题，但这在您提到的情况下应该会有所帮助。