匈牙利方法：由什么组成，示例 - 杜达斯 - 2025

该匈牙利方法是在分配问题，当你想降低成本使用的算法。也就是说，它用于通过根据最低成本将多个人分配给各种活动来找到最低成本。每个活动必须分配给不同的人。

分配问题是线性规划问题的一种特殊类型，其目标是最大程度地减少由多人完成多个工作的成本或时间。

资料来源：foto.com

分配问题的重要特征之一是只有一个工作（或工人）被分配给一台机器（或项目）。

这种方法是由匈牙利数学家D. Konig开发的。因此，它被称为分配问题的匈牙利方法。它也称为Kuhn-Munkres分配算法。

通过应用此方法（包括两个阶段），可以轻松解决任何分配问题：

-在第一阶段，进行行减少和列减少。

-在第二阶段，以迭代方式优化解决方案。

匈牙利的方法是什么？

匈牙利方法包括四个步骤。前两个步骤仅执行一次，而步骤3和4重复执行，直到找到最佳分配。

n到n阶的方阵被视为输入数据，该数据只能包含非负元素。

对于给定的问题，如果矩阵中的行数不等于列数，则视情况而定，必须添加一个哑行或哑列。这些虚拟单元的分配成本始终分配为零。

步骤1：减去每一行的最小值

对于数组中的每一行，将选择值最低的元素，并从该行的每个元素中减去。

步骤2：从每列中减去最小值

同样，为每列选择值最低的项，并从该列的每一项中减去。

步骤3：以最少的行数覆盖所有零

必须使用最少数量的水平和垂直线（无论是行还是列）覆盖从步骤2得到的矩阵中的所有零。

如果需要总共n条线来覆盖所有零，其中n等于矩阵大小n乘以n，则将获得零之间的最佳分配，因此算法将停止。

否则，如果需要少于n行以覆盖数组中的所有零，请继续执行步骤4。

第4步：创建额外的零

选择矩阵的最小元素（称为k），该最小元素未被步骤3中的任何一条线覆盖。

从未被行覆盖的所有元素中减去k的值。随后，将ka的值添加到两条线的交点所覆盖的所有元素上。

单行覆盖的项目保持不变。执行此步骤后，您返回到步骤3。

最优分配

在步骤3中停止算法后，选择一组零，以使每一行和每一列仅选择一个零。

如果在此选择过程中，行或列中没有单个零，则将选择这些零之一。该列或行中的其余零将被删除，并对其他分配也重复相同的操作。

如果没有单个零分配，则有多个解决方案。但是，对于不同的作业集，成本将保持不变。

删除所有已添加的虚拟行或列。因此，在此最终矩阵中选择的零对应于原始矩阵中所需的理想分配。

例

让我们考虑一家公司，其中有四个活动（A1，A2，A3，A4）必须由四个工人（T1，T2，T3，T4）执行。必须为每个工人分配一项活动。

以下矩阵显示了将特定工作人员分配给特定活动的成本。目的是最小化由这四个活动组成的任务的总成本。

步骤1：减去每一行的最小值

首先从该行的其他元素减去每行中具有最小值的元素。例如，第一行中的最小元素为69。因此，第一行中的每个元素都减去69。结果矩阵为：

步骤2：从每列中减去最小值

以相同的方式，从该列的其他元素中减去每列最小值的元素，得到以下矩阵：

步骤3：以最少的行数覆盖所有零

现在，我们将确定覆盖矩阵中所有零所需的最小行数（水平或垂直）。可以使用3行覆盖所有零：

由于所需的行数为三，并且小于矩阵的大小（n = 4），因此我们继续执行步骤4。

第4步：创建额外的零

选择了未被线覆盖的最小元素，其值为6。从未被覆盖的所有元素中减去该值，并将相同的值添加到两条线的交点覆盖的所有元素中。结果为以下矩阵：

如匈牙利方法所示，必须再次执行第三步。

步骤3（重复）

再次确定覆盖矩阵中所有零的最小行数。这次需要四行：

因为所需的行数是4，等于矩阵的大小（n = 4），所以我们在矩阵的零之间有一个最佳分配。因此，算法停止。

最优分配

如方法所示，以下零的选择对应于最佳分配：

零的选择对应于原始成本矩阵中的以下最佳分配：

因此，工作人员1必须执行活动3，工作人员2，活动2，工作人员3，活动1，工作人员4必须执行活动4。此最佳分配的总成本为69 + 37 + 11 + 23 = 140。

参考文献

1. 匈牙利算法（2019）。匈牙利算法。摘自：hungarianalgorithm.com。
2. 研究（2019）。使用匈牙利算法来解决分配问题。摘自：study.com。
3. 智慧工作（2018）。匈牙利解决分配问题的方法-管理定量技术。摘自：witnessjobs.com。
4. Geeks for Geeks（2019）。分配问题的匈牙利算法。摘自：geeksforgeeks.org。
5. Karleigh Moore，内森·兰德曼（Nathan Landman）（2019）。匈牙利最大匹配算法。辉煌。摘自：brilliant.org。