问题标签 [hungarian-algorithm]

我有一个分配问题，我想向 SO 社区询问为我的 spark 数据框（使用 spark 3.1+）实现此功能的最佳方法。我将首先描述问题，然后再进行实施。

问题是：我有最多 N 个任务和最多 N 个个人（在这个问题的情况下，N=10）。每个人都有执行每项任务的成本，其中最低成本为 0 美元，最高成本为 10 美元。这是一个匈牙利算法问题，有一些注意事项。

1. 在某些情况下，任务少于 10 个和/或个人少于 10 个，可以不为某人分配任务（或不为任务分配个人）。
2. [更复杂的边缘情况/我遇到麻烦的情况] - 列表中可能有一项具有标志的任务multiTask=True（不能超过 1 multiTask，并且可能没有）。如果一个工人的成本低于多x任务，他会被自动分配给多任务，并且在优化期间考虑多任务。
   • 我将分享几个例子。在此示例中，要分配给多任务的 x 值为 1。
     • 如果 10 名工人中有 1 名在多任务上的成本为 0.25，则将他分配给多任务，然后将其他 9 名工人分配给其他 9 个任务
     • 如果 10 个工作人员中有 2 个工作人员在 multiTask 上的成本 < 1，则他们都被分配到 multiTask，然后其他 8 个工作人员将被分配到其余 9 个任务中的 8 个。1 项任务不会分配给任何人。
     • 如果所有 10 个工作人员在 multiTask 上的 cost < 1，则所有这些工作人员都分配给 multiTask。这是非常罕见但可能的。
     • 如果在 multiTask 上没有任何 worker 的 cost < 1，则在优化过程中 multiTask 将只分配给一个人以最小化成本。

这是 spark 数据框的样子。注意：为了简单起见，我展示了一个 N=3（3 个任务，3 个个人）的示例。

您会看到有一个日期/位置，因为我需要为每个日期/位置分组解决这个分配问题。我打算通过使用dense_rank()然后使用 pandas UDF 为每个工作人员和任务分配一个“索引”来解决这个问题，然后根据索引填充 N x N numpy 数组，然后调用该linear_sum_assignment函数。但是，我不相信这个计划会奏效，因为我在 multiTask 中布置了第二个边缘案例。

如您所见，这种情况根本没有涵盖多任务。我想以最有效的方式解决这个问题，所以我不依赖于 pandas udf 或 scipy。

我需要为此类任务实现匈牙利算法的实现：我有任何矩阵示例（实际上我需要这个用于聚类分析）：

为了获得这样的结果，我需要对行或列进行一些排列：所有对角线元素都应该是最大的。在这里，我将展示一些照片：，其中我有 3 行和 3 列，然后我必须有一个结果： 。

如图所示，有一个排列：第一列变成第三列，之后新的第一列和第二列改变位置。我怎么能用匈牙利算法做这样的事情？

我想在非方形 numpy 数组上使用 python 中的匈牙利分配算法。

我的输入矩阵X如下所示：

X所需的结果是排序的矩阵，例如X_desired_output：

在这里，我想最大化成本而不是最小化，因此算法的输入在理论上要么是，要么是1-X简单X的。

我发现https://software.clapper.org/munkres/导致：

我怎样才能使用这些来排序X？jj仅包含 6 个元素，而不是原始的 7 列X。

我正在寻找实际排序的矩阵。

我正在使用 PyTorch 进行神经网络训练。我试图训练我的网络来替代匈牙利算法。我对成本矩阵中的每一行都有神经网络，大小为 500x500 - 包含 500 个列表的列表，每个列表包含 500 个元素。对于训练，我将每个矩阵中的一个特定行（包含 500 个元素的列表）作为输入传递，分配索引作为输出传递。批量大小为十。因此，每批包含 10 个列表的列表，每个列表包含 500 个元素，并且列表具有 10 个整数作为已分配给每一行的索引。

这对的第一个元素作为 net 的输入传递，第二个元素用于损失计算

正如我想象的那样，我必须将一批行作为输入传递，并将为此行索引分配的一批作为输出传递

但最终损失在 6.2 附近停止，并且不再减少。可能是我失去了一些基本概念。提前感谢您的帮助

我有工作和员工的数据框，每个员工可以完成每项工作的持续时间。我想使用匈牙利算法将每个工作分配给 1 个员工，每个员工只能分配 1 个工作。

这是数据：

预期的结果是：

然后打印出来：

谁能帮我解决这个问题？提前致谢！

我正在尝试使用匈牙利算法根据学生的喜好将学生分类。

在我的数据集中，大约有 550 名学生，每个学生都有一个排名前 5 的偏好列表。每个首选项都是一个对应于一个类的 ID。每个班级都有最小和最大容量（在我的例子中，最小上限为 15 人，最大上限为 27 人），数据集中有 21 个班级。

这是每个学生的示例数据集：

这是每个类的示例数据集：

我需要将学生分类到他们喜欢的班级，同时还要遵循最小容量和最大容量。为此，我打算使用匈牙利算法。

因为有大约 550 名学生和 21 个班级，并且为了让匈牙利算法起作用，我打算制作这些班级的“副本”。我会首先为每个班级（如班级 1.1、1.2、1.3、1.4、2.1、2.2、2.3 等）制作 15 个副本，以满足班级的最低要求，然后将更多副本添加到其中最受欢迎的班级直到有相同数量的学生和班级副本。

然后，根据学生的副本和偏好，我正在考虑制作一本字典并使用该算法的实现。

我有几个问题：

1. 这个计划是一个好的计划还是有更好的解决方案来解决我遇到的问题？
2. 如何制作所有链接回原始 ID 的类的副本？
3. 在将其实现到算法中时，我应该将学生的偏好放入字典中（如 GitHub 链接所示），但如果现在有 1.1 之类的 ID，人们的选择是 1，并且没有像这样的实际类算法，我应该如何解决？

提前谢谢您，如果您需要任何澄清，请告诉我

我需要根据学生的喜好将他们分类，我打算使用匈牙利算法对他们进行分类。我遇到的问题是人数多于班级，每个班级都有最少的人数。

在我的数据集中，大约有 550 名学生，每个学生都有一个排名前 5 的偏好列表。每个首选项都是一个对应于一个类的 ID。每个班级都有最小和最大容量（在我的情况下，最小上限为 15 人，最大上限为 27 人），数据集中有 21 个班级。

这是每个学生的示例数据集：

这是每个类的示例数据集：

因为有大约 550 名学生和 21 个班级，并且为了让匈牙利算法起作用，我打算制作这些班级的“副本”。我会首先为每个班级（如班级 1.1、1.2、1.3、1.4、2.1、2.2、2.3 等）制作 15 份副本，以满足班级的最低要求，然后将更多副本添加到其中最受欢迎的班级直到有相同数量的学生和班级副本。

我的问题是：我将如何循环变量的复制，这些变量在算法中就像他们自己的类或类的选择一样（因为选择也需要不同，以便将人们放在同一类的不同副本中并且当有其他副本时不让他们只竞争一个变量）但是在排序完成后，副本可以追溯到原始吗？

提前谢谢你，如果有什么我可以澄清的，请告诉我