Python中的Hungarian算法

引言

作为一名信息研究员或程序员，当需要以最佳方式分配资源给任务时，你经常会遇到优化困难。其中一个问题就是分配问题，我们需要根据成本或价值来决定如何最好地分配资源给任务。解决这个问题的流行方法之一是匈牙利算法。本文将探讨匈牙利算法，并在 Python 中进行实现。

什么是分配问题？

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

线性分配问题需要最大化可用的资源数量，同时最小化花费的金额。例如，考虑下面的 2D 网格，其中每一行代表一个特定的供应商，每一列代表聘请该供应商生产特定商品的成本。每个供应商仅限于专门生产其中一种产品。对于网格中的每个列和行，只能选择一个元素，并且所选元素的总成本应被最小化（最小成本使用）。

匈牙利算法：概述

匈牙利算法（也称为 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。

为了理解该策略，请考虑以下示例：

设二维数组为：

步骤 1：从每行中减去最小值。分别从第 1、2 和 3 行中减去 2、3 和 2000。

步骤 2：从每列中减去最小值。分别从第 1、2 和 3 列中减去 0、1500 和 0。

步骤 3：用最少数量的水平线和垂直线覆盖所有零。

步骤 4：发现最优分配，因为需要三条线来覆盖所有零。

因此，最佳成本为 4000 + 3500 + 2000 = 9500。

目标是使用 dlib 包中的 `max_cost_assignment()` 函数来构建过程。匈牙利算法，有时也称为 Kuhn-Munkres 算法，在该函数中实现，并需要 O(N^3) 的时间来完成。这样就解决了最佳分配问题。

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

输出

5

• 时间复杂度：O(N^3)
• 辅助空间：O(N^2)

结论

匈牙利策略是一种快速解决分配问题的有效方法。该算法通过在二分图中寻找增广路径来确定最佳分配，以最小化成本或最大化价值。本文分析了匈牙利技术，并在 Python 中使用了 SciPy 包。作为一名信息研究员或程序员，您可以使用这项技能来利用匈牙利算法解决作业分配问题。

匈牙利策略只是可用的多种优化算法之一；在为特定情况选择最佳算法之前，理解约束和问题上下文至关重要。