问题标签 [hungarian-algorithm]

在这里，我提供了我的问题的最小完整可验证示例：

考虑大小为 3 X 17 的矩形矩阵：行 = [10,6,9] 考虑。其中列是模式，每个模式都与一个值相关联

现在，列值和行值之间的差异被视为矩阵 3 X 17 中的成本，如果成本结果为负，则将其替换为所有列值的总和（没有什么特别的，但要确保一些巨大的价值）。现在需要进行最低成本分配。我使用sudo apt-get install python-munkres安装了库munkres 并运行了以下代码：

生成以下输出：

问题是 [2,5],[1,5],[3,4] 是最终分配的模式，对应于最低成本。这里的模式 [2,5],[1,5] 不是相互排斥的。“5”有共同之处。一旦 r1 得到 [2,5] 分配，则包含已分配元素的其余模式 ie,2,5 此处不应可用于分配，或者矩阵中相应的模式相关成本应更新为太高的值，这样那些不再考虑到下一行的人应该像这样进行。

最终意味着如果分配是可能的，则相应的模式本质上应该是互斥的。

谁能建议如何解决这个问题？

我目前正在编写一个将学生映射到课程的程序。目前，我正在使用 SAT-Solver，但我正在尝试实现一个多项式时间/非贪婪算法来解决以下子问题：

• 有学生（50-150）
• 有科目（10-20），例如“数学”、“生物学”、“艺术”
• 每个科目有课程（至少一门），例如'math-1'、'math-2'、'biology-1'、'art-1'、'art-2'、'art-3'
• 学生选择一些（固定）科目（10-12），并且对于每个科目，学生必须被分配到现有课程中的一门（如果可能）。选择“math-1”或“math-2”这门课程并不重要。
• 课程有最大允许学生人数（20-34）
• 每门课程都在一个固定的块中（= 时隙 1 到 13）
• 不得将学生分配到同一块中的课程

我现在描述我到目前为止所做的事情。

(1) 忽略 course-student-limit

我能够用匈牙利算法/二分匹配解决这个问题。每个学生可以通过如下建模来单独计算：

• 左节点代表科目“数学”、“生物学”、“艺术”（学生的）
• 右节点代表块'1'，'2'，....'13'
• 为从“主题”到“块”的每门课程插入一条边

这样，学生被分配到每个科目的课程，而不参加同一块中的课程。但是 course-limits 被忽略了。

(2) 忽略学生选择的科目

我能够用最大流量算法解决这个问题。为每个学生建模以下内容：

• 第 1 层：从源到每个学生，流量为 13
• 第 2 层：从每个学生到他/她的个人区块，流量为 1
• 第 3 层：从每个学生块到该块中的每个课程，流程为 1
• 第 4 层：从每门课程到具有“最大学生限制”的接收器

这样，学生可以选择任意课程并且课程限制已满。但他/她可能不走运，被分配到'math-1'、'math-2'和'math-3'，忽略了'生物学'和'艺术'科目。

(3) 贪婪的匈牙利语

我的另一个想法是一次将一个学生与匈牙利算法匹配并调整权重，以便首选“更多空课程”。例如，可以建模：

• 左节点是学生的主题
• 右节点是块
• 为每门课程插入一条从主题到课程块的边，权重 = 空闲座位数

然后计算最大权重匹配。

我真的很感激任何建议/帮助。

谢谢！

我有一个问题困扰了我一段时间。

我们有“工人” w_0、w_1 ... w_n，以及任务 t_0、t_1、... t_m 和持续时间 D_ij，这样 w_i 可以在该小时数内完成 t_j。每个工人还有最多 m_0,m_1... m_n 可以工作的小时数。

多个工人可以按比例完成同一任务。例如，如果 D_11 = 2 和 D_21 = 4，那么工人 1 在任务 1 上的效率是工人 2 的两倍。所以你可以结合，例如 1 的 1 小时和 2 的 2 小时来完成任务。

我们如何确定可以完成所有任务的最少小时数。

我曾尝试使用贪心技术为每项任务选择最佳工人，但这不适用于每种情况。例如，工人 1 可以在 2 小时内完成任务 1，在 4 小时内完成任务 3。很明显，工人 1 将被选中从事任务 1，即使假设任务 3 对其他工人来说非常耗时，而工人 1 本来是完美的工作。

我曾考虑将问题简化为分配问题，但没有找到方法。

如何解决这个问题？

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

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

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

编辑：

Sascha 提出的正式描述：

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

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

在哪里

约束将是：

和

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

我正在关注印度人在 Youtube 上关于匈牙利问题的教程。我在他决定下一步要选择哪些行和列的地方进行堆叠。他的例子没有我面临的问题。这是我的示例表：

所以让我们一步一步开始行和列的选择：

1. 第一行包含 >1 个零 => 转到下一行
2. 选择 (2,1) 零并将 (5,1) 添加到暂停的零
3. 第三行包含 >1 个零 => 转到下一行
4. 选择 (4,6) 零
5. 选择 (5,1) 零并将 (3,1) 添加到暂停的零
6. 选择 (6,5) 零并将 (3,5), (1,5) 添加到暂停的零

现在，剩下的零是 (1,3), (1,4), (3,3), (3,4)

我找不到处理它们的方法，也找不到按列或按行的方法。我该怎么处理它们？

这是最后的表格：

在哪里

• su=暂停
• se=选中
• ? = 我应该做什么

找到 n*n 2D 矩阵的元素的最小总和，这样我必须从每一行和每一列中选择一个且只有一个元素？例如

如果我4从行中选择，1我也不能从 列中选择12行，我只能从第 2 行第 2 列中选择 6。11

所以同样的最小总和将4 + 6 = 10是6第二行第二列的位置

而不是第二行第一列的6 + 12 = 18位置6

也4 + 12不允许，因为两者都来自同一行

我想到了蛮力，一旦我从行和列中选择元素，我就无法选择另一个，但这种方法是O(n!) .

我已经查看了解决分配问题的匈牙利算法的几种解释，其中绝大多数都涵盖了非常简单的情况。

我找到的最容易理解的解释是YouTube 视频。

我可以对算法进行编码，但我担心一种特殊情况。如果你看视频的话，31:55到37:42解释了相关案例，但我会在下面解释。

我应该首先提到我将处理一个 300 x 300 的矩阵，所以目视检查是不可能的。此外，我需要找到所有最小分配。换句话说，如果有多个赋值产生相同的最小值，我需要找到它们。

这是我关心的特殊情况。您可以在 YouTube 视频中看到这一点，但我会在这里详细介绍。我们从这个矩阵开始：

当我们减少行和列时，我们得到：

（让我提一下，我可以直观地看到这个矩阵有 4 个解，总分是 13。）

给定上面的简化矩阵，任何行或列都没有唯一的零，所以，根据视频中描述的算法，我可以任意选择任何零元素进行赋值，所以我选择(1,1)。

我将用星号标记分配的零，并在不再可供考虑的行和列中的那些零旁边放置一个“x”。现在我们有了这个：

接下来，我们继续检查行中是否存在唯一的零。我们在 (3,2) 处找到一个，所以我们用星号标记它，并用“x”标记不可用的零：

接下来，我们开始在列中寻找唯一的零（因为所有行都已用尽）。我们发现第三列在 (2,3) 处有一个唯一的零，所以我们标记它：

此时，没有更多可用的零，并且第 4 行未分配。（这个特定的 YouTube 视频现在使用“滴答程序”，这是确定覆盖所有零所需的最少行数的常用技术。如果您不熟悉这种技术，从14:10到 16 开始解释： 00，尽管演示者使用的矩阵与此处显示的矩阵不同。）“勾选程序”是这样的：

1. 勾选所有没有分配零的行（第 4 行）。
2. 对于勾选的每一行，勾选该行中包含零的列。
3. 对于在步骤 2 中勾选的每一列，勾选已分配零的相应行。
4. 重复第 2 步和第 3 步，直到无法再打勾为止。
5. 在所有勾选的列和未勾选的行中画线。

此时，滴答程序生成 4 条垂直线，覆盖全零。四个垂直线告诉我们矩阵中的零代表一个或多个解决方案，但是，正如我们所见，第 4 行是未分配的。尽管有四条垂直线，第四行仍未分配的事实告诉我们，我们选择了错误的零进行分配！

视频的演示者指出这个问题是我们对元素 (1,1) 的初始（任意）分配的结果。演示者说，“有更复杂的方法可用”让我们摆脱这种情况，但他没有解释这些技术是什么。他暗示存在选择零的“智能”方法，而不是我们用来在 (1,1) 处选择零的任意选择。

面对进行任意分配时，我可以采取的一种方法（我不确定它是否是最好的）是从可用任意选择数量最少的行或列进行分配。在此示例中，这意味着我将从只有两个任意选择的第 3 行或第 4 行进行任意分配，而不是从有四个任意选择的第 1 行或第 2 行进行。当然，因为我需要所有正确的解决方案，所以无论何时进行任意分配，我都必须遍历所有可用的任意分配。例如，如果我选择 (3,1) 作为任意分配，我还必须稍后分配 (3,2)。

那么，我的问题是，当我面临任意选择零进行赋值的选择时，最好的方法是什么？是我在上一段中提到的吗？我怎样才能消除如图所示的死胡同？请记住，我仍然需要枚举所有具有相同最低分数的解决方案。

我已经在 C 中实现了匈牙利算法。在大多数情况下，它运行良好。有时，我的代码无法找到某些矩阵的解决方案。检查解决方案我开始认为矩阵的覆盖方式很重要。这是一个例子：

这是执行前两个步骤时的矩阵（每行减去 min，每列减去 min

当使用我的代码覆盖时（2 个含义元素被交叉 2 次）：

我在这里使用相同的原始矩阵寻找解决方案，它们以不同的方式覆盖矩阵。他们没有选择最后两列，而是选择了最后两行。通过再减少两个矩阵，它们最终得到匹配。另一方面，我没有。

有没有办法决定哪条线路组合更好？

假设我有一个设备矩阵及其统计数据。帽子，衬衫，裤子，靴子。每个内部数组的大小可以不同，但​​总会有一定数量的内部数组——在本例中为 4。

我想通过矩阵找到最佳路径，然后以这样一种方式删除一个项目，即确定的下一条路线（以及路线的总和）是第一条之后的下一个最佳路线。在这个例子中，[9, 8, 3, 9]最好，对吗？所以我们可以删除9[0] 中的 a 以达到8仅 1 的下降。

我可以总结所有可能的路线并从那里确定它，但内部数组的大小可能比显示的要大得多。

我花了一些时间思考它，并研究了周围。我唯一能看到的是匈牙利算法，但它现在超越了我的数学/计算知识。在这种情况下，这会是最适用的知识吗？它似乎可以满足路线的最低“成本”，但我需要相反。

我的想法，至少作为一个想法：

1. 拉出每个内部数组中的最高数字，从中创建新数组。对此 [0] 进行排名。
2. 将每个内部数组中的最大数字与下一个最小数字进行比较。排序每个之间的差异。
3. 从 #2 中找到的具有最小差异的内部数组中删除最大的数字。
4. 重复 #1 到 #3。

在上面的示例中，我期望如下所示。

编辑：我想我扼杀了这个问题的解释，让我稍微修正一下。

EDIT2：本质上是跨集的最小损失，仅从一个内部数组中删除一项。

我对分配问题并不精通，并试图找到一种替代 Munkres/匈牙利方法的替代方法，该方法适用于分配问题的变体，其中：

1. 某些作业是不允许的
2. 可能无法将每个人/行分配给一个分配/列（在这种情况下，我只想进行尽可能多的分配 - 也许通过找到并使用最大的可解矩阵）

我已经能够修改 Munkres 实现来处理 #1，但它在以下情况下会崩溃：

最终无法通过：

我应该使用另一种算法来处理这个问题吗？或者在将其传递给算法之前使用某种算法方法来检测上述无法解决的情况（如果我每次都首先运行算法来检测这些情况会变得相当昂贵）？

作为参考，这是我正在使用的代码（在 Python 中）： https ://github.com/knyte/munkres/blob/master/munkres.py