匈牙利算法 Python

引言

作为一名数据科学家或软件开发人员，您可能经常在分配资源以最高效的方式完成任务时遇到效率问题。其中一个问题是分配问题，我们需要根据成本或价值来确定如何最佳地分配资源给任务。解决此问题的一种流行方法是匈牙利算法。在本文中，我们将探讨匈牙利算法并在 Python 中实现它。

什么是分配问题？

您可以如下定义分配问题：给定一组资源和一组任务，其中每种资源只能用于一项任务，并且每项任务只需要一种资源，我们必须选择一个分配，以使总成本最小化或总价值最大化。这个问题出现在各种领域，包括匹配问题、工作调度和生产计划。

简单的分配问题代表了在最小化支出的同时最大化可用资源数量的需求。举个例子，考虑下面的二维网格，其中每一行代表一个特定的供应商，每一列代表雇佣该供应商生产特定商品的成本。每个供应商最多只能专精于生产其中一种商品。对于网格中的每个列和行，只能选择一个元素，并且必须最小化所选元素的完成（最小成本支出）。

匈牙利算法：概述

匈牙利算法（有时也称为 Kuhn-Munkres 算法）是一种用于在多项式时间内解决分配问题的强大方法。它使用组合优化技术来识别最佳分配。该方法通过“对偶性”技术来改进问题，并依赖于在二分图的增广路径。

匈牙利算法用来确定最佳分配的步骤如下：

• 创建成本矩阵：通过构建一个网格来创建成本矩阵，该网格的行代表每个资源，列代表每个任务，元素代表使用该资源完成该工作所需的成本或收益。
• 初始化分配矩阵：为了表示资源到任务的分配，构建一个与成本矩阵尺寸相同的第二个网格，该网格最初用零填充。
• 约简矩阵：为了便于识别最佳分配，对成本矩阵应用行和列的约简。在此阶段，应从每一行和每一列的其余元素中减去该行和该列的最小元素。
• 找到初始可行解：通过以确保任何行或列不超过一项任务的方式分配资源来找到初始可行解。为此，请通过约简矩阵中的零绘制边界线。
• 增广分配：为了改进分配，在约简矩阵中找到最少的未覆盖元素，如果初始解不是最优的，则将其从所有未覆盖元素中减去。然后将其添加到被两条线覆盖的每个元素上。持续执行此操作，直到找到最佳分配。
• 改进分配：如果分配尚不完美，请对矩阵的行进行调整，以开辟更多路径增广的可能性。应重复之前的过程，直到获得最佳分配。
• 提取分配：一旦确定了最佳分配，就将其从分配矩阵中提取出来，并将其作为问题的解决方案提供。

匈牙利算法的 Python 实现

scipy 库有一个名为 linear_sum_assignment 的函数，该函数应用匈牙利方法来解决分配问题，使我们能够在 Python 中实现匈牙利算法。这是一种如何应用它的示例：

在此示例中，我们构建了一个成本矩阵来表示将三个资源分配给三个任务的成本。然后使用 linear_sum_assignment 函数找到最佳分配。该函数返回的两个数组 row_indices 和 col_indices 包含最佳分配的行和列索引。然后提取分配，并打印结果。

给定一个 N*N 的二维数组 arr，其中 arr[i][j] 表示第 i 个工人完成第 j 个任务的成本。任何工人都可以被分配执行任何任务。目标是分配任务，以便每个工人一次只能专注于一项任务，同时使分配的总成本最小化。

示例

在本文中，描述了许多解决此问题的方法。

方法：将使用匈牙利算法来解决此问题。算法工作原理如下：

• 找到矩阵中每一行的最小元素，并将其从该行中的其他每个元素中减去。
• 对每一列重复步骤 1。
• 使用最少数量的水平和垂直线完全填充矩阵中的零。
• 最优性检验：如果覆盖线的数量最少是 N，则可以实现最优分配。否则，如果线的数量少于 N，则未发现最优分配，必须执行步骤 5。
• 找到未被线覆盖的最小项。该项应从每个未覆盖的行中减去，并添加到每个覆盖的列中。返回到步骤 3。

为了理解该方法，请考虑以下示例：

目标是使用 dlib 包中的 max_cost_assignment() 函数来构建上述过程。该函数实现了有时称为 Kuhn-Munkres 算法的匈牙利算法，并以 O(N^3) 的时间复杂度完成。解决了最佳分配问题。

上述策略的应用如下所示：

输出

5

时间复杂度：O(N^3)

辅助空间：O(N^2)

结论

匈牙利方法是一种有效的方法，可以快速解决分配问题。该算法通过在二分图中利用增广路径来最小化成本或最大化价值，从而确定最佳分配。在此，我们研究了匈牙利方法，并使用 scipy 库在 Python 中实现了它。作为数据科学家或程序员，您现在可以利用这项技能在自己的项目中利用匈牙利算法来处理作业问题。

匈牙利方法只是众多优化算法中的一种；在选择最佳算法来处理特定情况之前，了解约束和问题上下文至关重要。