详细内容或原文请订阅后点击阅览
最佳分配和匈牙利算法
匈牙利算法在行动！作者提供的图片。本文提供了匈牙利算法如何在图上解决最优分配问题的分步示例我写这篇文章的原因是我花了几天时间才理解匈牙利算法如何在图上工作。矩阵版本更容易理解，但它没有提供所需的洞察力。我在网上找到的所有优秀信息都无法提供直观理解算法为何这样做所需的清晰度。我也很难将算法描述转化为工作示例。虽然我们今天拥有的各种 LLM 工具有助于以各种方式重新表述算法的描述，但当我要求它们生成一个工作分步示例时，它们都失败了。所以我坚持生成了一个匈牙利算法在图上发挥其魔力的示例。我在这里一步步介绍这个示例以及我从这个练习中获得的直觉，希望它能帮助其他人学习这个奇妙的算法来解决最优分配问题。最优分配问题是从一组节点到另一组节点找到一对一匹配，其中每对节点之间的边都有一个与之相关的成本，并且生成的匹配必须确保总成本最小。这个问题很普遍。它可以将一组人分配给一组工作，每个工作都有
来源:走向数据科学最佳分配和匈牙利算法
最佳分配和匈牙利算法
本文提供了匈牙利算法如何解决图上最佳分配问题的分步示例
我写这篇文章的原因是我花了几天时间才理解匈牙利算法如何在图上工作。矩阵版本更容易理解，但它没有提供所需的洞察力。我在网上找到的所有优秀信息都无法提供直观理解算法为何这样做所需的清晰度。
我也很难将算法描述转化为一个可行的示例。虽然我们今天拥有的各种 LLM 工具都以各种方式帮助重新表述算法的描述，但当我要求他们生成一个可行的分步示例时，它们都失败了。所以我坚持生成一个匈牙利算法在图上发挥其魔力的例子。我在这里介绍这个分步示例以及我从这个练习中获得的直觉，希望它能帮助其他人尝试学习这个奇妙的算法来解决最佳分配问题。
最佳分配问题是从一组节点到另一组节点找到一对一匹配，其中每对节点之间的边都有与之相关的成本，并且生成的匹配必须确保最小总成本。
二分 完整在此示例中，我们需要将 4 个人映射到 4 辆出租车。我们可以强制解决方案：