原文：
towardsdatascience.com/optimum-assignment-and-the-hungarian-algorithm-8b1027628028?source=collection_archive---------1-----------------------#2024-07-07
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/55cb3b2d5fc4198c9f32a81ef3ee708a.png
匈牙利算法在实际应用中的效果！图片来自作者。
本文提供了一个逐步示例，展示了匈牙利算法如何在图上解决最优分配问题。
https://medium.com/@prasannasethuraman?source=post_page---byline--8b1027628028--------------------------------https://towardsdatascience.com/?source=post_page---byline--8b1027628028-------------------------------- Prasanna Sethuraman
·发表于 Towards Data Science ·11 分钟阅读·2024 年 7 月 7 日
–
我写这篇文章的原因是因为我花了几天时间才理解匈牙利算法在图上的工作原理。矩阵版本更容易理解，但它没有提供所需的洞察力。我在网上找到的所有优秀资料都未能让我清晰地理解算法为什么要按这样做。
对我来说，将算法描述转化为一个可工作的示例并不简单。尽管我们今天拥有的各种大型语言模型（LLM）工具帮助我用多种方式重新措辞算法描述，但当我要求它们生成一个逐步的工作示例时，它们都失败了。所以我坚持不懈地生成了一个匈牙利算法在图上应用的示例。我在这里展示这个逐步示例以及从这次练习中获得的直觉，希望能帮助其他想学习这个精彩算法以解决最优分配问题的人。
最优分配问题是从一组节点到另一组节点找到一对一匹配，其中每一对节点之间的边都有一个相关的成本，生成的匹配必须确保总成本最小。
这个问题是普遍存在的。它可以是将一组人分配到一组工作，每个工作需要为特定工作支付特定的价格，然后问题就是将人分配到工作上，以使总成本最小化。它也可以是将一组可用的出租车分配给需要出租车的一组人，每辆出租车需要特定的时间到达特定的人。每次我们预定 Uber 或 Ola 时，都会使用匈牙利算法来解决这个问题。
分配问题最好用二分图来表示，二分图是一个具有两个不同节点集的图，且边从不连接同一集合中的节点。我们以出租车匹配问题为例，二分图显示了节点之间的所有可能连接。边的权重表示特定出租车到达特定人的时间（以分钟为单位）。如果一个集合中的所有节点都与另一个集合中的所有节点连接，则该图被称为完全图。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/b4acbdcaf63a667f569f17df254c2e37.png
用于出租车匹配问题的二分图。图片由作者提供
在这个例子中，我们需要将 4 个人映射到 4 辆出租车上。我们可以暴力破解求解：
对于第一个人，有四个可能的出租车分配，我们可以选择其中任何一辆
对于第二个人，剩下三辆出租车，我们从这三辆中选择一辆
对于第三个人，我们选择剩下的两辆出租车中的一辆
对于最后一个人，我们选择剩余的出租车
所以可能的分配总数是 4 x 3 x 2 x 1，即 4 的阶乘。然后我们计算所有这些 4!种分配的总成本，并选择成本最低的那一项。对于较小规模的分配问题，暴力破解仍然是可行的。但是随着n（人或出租车的数量）的增加，*n!*会变得非常大。
另一种方法是贪心算法。你选择一个人，将最小成本的出租车分配给他，然后选择下一个人，给他分配剩余出租车中最小成本的那一辆，以此类推。在这个例子中，对于最后一个人，不可能进行最小成本分配，因为可以最短时间到达他的出租车已经分配给了另一个人。所以算法选择了下一个可用的最小成本出租车。因此，最后一个人由于其他人的贪心而受到影响。贪心算法的解决方案可以在这里的图中看到。虽然在这个例子中，贪心方法确实达到了最低成本 36，但不能保证这种贪心方法会得到最优分配。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/895c54d2aa90a05c20171682b1416de6.png
贪心分配。图片由作者提供
匈牙利算法提供了一种高效的寻找最优解的方法。我们将首先从矩阵算法开始。我们可以将图表示为一个邻接矩阵，其中每条边的权重是矩阵中的一个条目。图和其邻接矩阵可以在这里看到。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5e91b79c0c7c5d967e5103dba7df0a2a.png
二分图及其邻接矩阵。图片由作者提供
这里是匈牙利算法在邻接矩阵上操作的步骤：
对于邻接矩阵中的每一行，找出并减去该行所有条目的最小值。
对于邻接矩阵中的每一列，找出并减去该列所有条目的最小值。
用最少的线覆盖矩阵中的所有零。
a. 计算每一行和每一列中的零的数量
b. 首先在零最多的行/列上画线，其次是零第二多的行/列，以此类推。
c. 如果覆盖所有零所需的线数少于矩阵的行/列数，则继续执行第 4 步，否则进入第 5 步
找到未被线覆盖的最小条目，并将该条目从所有未覆盖的条目中减去，同时将它添加到所有被两条线（水平线和垂直线）覆盖的条目中，然后进入第 3 步。
可以通过从仅有一个零的行/列开始来生成最佳分配。
前两步很简单。第三步需要按照零的数量从高到低的顺序划去行或列。如果划去的行和列的数量不等于需要匹配的节点数，则需要创建额外的零——这在第四步中完成。重复执行第三步和第四步，直到划去足够的行和列。这样，矩阵中就有足够的零用于最佳匹配。
这个出租车匹配示例的匈牙利算法步骤显示在这个动画 GIF 中。
匈牙利算法在邻接矩阵上的动画。图片由作者提供
对于那些难以跟随 GIF 动画的人，这里是显示步骤的图片。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/1e56334c78b24df7e4b3813f3ac00bd5.png
匈牙利算法在邻接矩阵上的应用。图片由作者提供
算法在已划去的行/列数等于需要匹配的节点数时终止。最后一步是找到分配结果，可以通过首先分配对应零条目的边来轻松完成，在这个例子中，可能是(P1,T2)，通过选择第一行中的第一个零。这样我们就不能再将 T2 分配给其他人，因此 T2 列中的第二个零可以被移除。P4 行中唯一剩下的零表示它必须分配给 T1，因此下一个分配是(P4,T1)。此时，T1 列中的第二个零也可以被移除，P2 行只剩下一个零。第三个分配因此是(P2,T3)。最后的分配就是(P3,T4)。读者可以通过加总这些分配对应的边的权重来计算总成本，结果为 36。
如果我们查看 GIF 动画，整个分配过程就更直观了，我们有一个连接所有节点的子图，并且我们可以创建一个交替路径，其中的边交替为已匹配（绿色）和未匹配（红色）。
现在我们已经看到了匈牙利算法在邻接矩阵上的应用，我们知道这些步骤为何是这样的了吗？究竟创建覆盖零的最小数量的线条告诉我们什么？为什么最小的线条数量必须等于要匹配的节点数量才能停止算法？我们如何理解步骤 3 中的这个奇怪规则，即要创建额外的零，我们需要找到未覆盖的最小值，将其从所有未覆盖的条目中减去，同时加到覆盖了两次的条目中？
为了获得更好的理解，我们需要看到匈牙利算法是如何在图上工作的。为此，我们需要将最优分配问题视为匹配需求和供应。这需要为每个节点创建标签，表示供应和需求的数量。
现在我们需要一些符号来解释这个标签过程。二分图中有两个不同的节点集合，我们称它们为 X 和 Y。所有属于集合 X 的节点用x表示，属于 Y 的节点用y表示。标签则分别为l(x)和l(y)，连接x和y的边的代价是w(x,y)。标签必须是可行的，这意味着当我们希望最小化成本时，l(x)+l(y)≤w(x,y)，而当我们希望最大化成本时，l(x)+l(y)≥w(x,y)。
在我们的例子中，人们的需求是他们必须立即乘坐出租车，零等待时间。出租车的供应是到达这些人所需的时间。初始的可行标签是，将每辆出租车到达四个乘客所需的最短时间作为出租车的标签，而乘客的标签则为零。
一旦我们有了可行的标签，我们就可以创建一个等式子图，其中我们只选择那些满足等式的边：l(x)+l(y)=w(x,y)。初始标签和结果等式子图（高亮显示的边）如图所示。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4fb56a29424e52afe0b14a487e61222c.png
初始标签的等式子图。图像由作者提供
我们看到在这个等式子图中有些节点没有连接，为了解决这个问题，我们需要修正标签。我们通过查看那些未连接的节点，并使用可以更新标签的最小值来更新这些节点的标签，以便建立连接。
在我们的例子中，如果 P3 的标签是 0，那么它无法连接。为了使这个标签增加到足以建立连接的最小值是 1，这个值是通过查看连接到 P3 的每一条边上的最小松弛（Δ=w(x,y)-(l(x)+l(y)))得出的。同样，对于 P4，其标签是根据它的边上的最小松弛来更新的。更新标签后的结果等式图在图中显示。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4d85d51a17f23065645997b913c5ad53.png
未连接节点的标签修正。图像由作者提供
我们现在可以尝试在等式子图上找到匹配，我们会看到只有 3 个节点可以匹配。这是因为在等式图中，我们还没有一条能够连接所有节点的交替路径。由于没有足够的边来创建这样的交替路径，我们需要再次修订标签以添加额外的边。但是这次，等式子图已经与所有节点建立了连接。所以我们这次添加的边应该有助于扩展交替路径。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/9c9df2010ed9465e1ac24da251518271.png
交替路径。图由作者提供
我们观察由该交替路径连接的所有节点（图中通过红色和绿色边表示），并提出问题：这些节点的标签可以通过什么最小松弛量进行修订以添加一条边。为了找到这个最小松弛量，我们查看所有连接到不在交替路径中的 X 节点的边的松弛量，如下一张图所示，并计算最小值。对于这个例子，最小松弛量是 2（来自边 P3-T3）。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/881925cf33ad093174c0ffb9510f1a6d.png
扩展交替路径的边选项。图由作者提供
交替路径中所有节点的标签需要更新，但当我们调整需求（通过添加最小松弛量），我们还需要从供应中减少相同的值（通过从中减去最小松弛量），以确保等式图中的现有边不发生变化。修订后的标签和更新后的等式图如图所示。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/a60d786a5d32ea7cfa94b137e8e937fb.png
标签修订后的等式子图。图由作者提供
我们现在可以看到，有一条交替路径连接了所有节点。现在可以通过使用交替路径并在匹配和未匹配的边之间交替来找到匹配（见图）。请注意，交替路径与每个节点有两条边相连。节点下方的数字表示交替路径连接这些节点的顺序。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/9b0c1c73797b8ef9dfcfb64a187af156.png
匈牙利算法在图上的结果。图由作者提供
可以通过从图中选择所有用绿色高亮的边来读取分配情况。也就是说，(P1,T4)，(P2,T1)，(P3,T3) 和 (P4,T2)，这将得到一个总成本 8+10+11+7 = 36。整个过程的动画可以在这里的 GIF 中看到。
匈牙利算法在图上的应用。图由作者提供
我们从图上的匈牙利算法看到，我们始终只通过添加一个额外边所需的最小值来调整供应和需求。因此，这个过程保证了我们最终能得到最优成本。这个过程的数学公式和证明在许多网上资源中都有清晰的阐述，但由于我们必须跟踪子图和子集，图的数学公式并不容易理解。一个展示这一过程的例子很有帮助，至少我希望是这样。
我们还可以看到与我们在邻接矩阵上所做的步骤之间的相似性。通过在图上应用算法获得的洞察，我们可以看出，覆盖零的最小线数需要等于要匹配的节点数，才能确保最大匹配。邻接矩阵中创建额外零的规则并没有提供直观的理解，但基于未包含在交替路径中的边的最小松弛对图上标签的修正，立即提供了连接。
话虽如此，操作矩阵的算法更容易理解和实现，这也是为什么网上有很多关于用这种方式解释匈牙利算法的信息。但我希望你们中的一些人同意我， 一旦我们看到匈牙利算法在图上的应用，这种清晰度为我们提供的理解程度是理解这个简洁算法的关键。
这篇文章到这里就结束了。我还录制了一段视频，介绍了这些内容，但视频时长为 45 分钟，因为我似乎随着年龄增长说话变得更慢了。也许有一天我会把视频链接放在这里。
