匈牙利算法详解：从基本概念到实现步骤

匈牙利算法详解：从基本概念到实现步骤

引用

CSDN

1.

https://m.blog.csdn.net/nuc_baixu/article/details/144240615

匈牙利算法（Hungarian Algorithm）是一种解决二分图最大匹配或最小加权完美匹配的算法。其主要用于解决如下问题：给定一个成本矩阵，找出一种方式将矩阵的每一行和每一列都匹配上，使得总成本最小。

算法实现步骤

1. 初始化

• 给定一个二分图，图的节点分为两部分（通常为左侧集和右侧集），边上有权重，目标是找到一个匹配，使得所有匹配的边的权重和最小。
• 为了简化描述，设定权重矩阵为 cost[i][j]，表示从左侧节点 i 到右侧节点 j 的边的权重。

2. 减法步骤

对于每一行，找到该行的最小元素，然后从该行的每个元素中减去这个最小值。这一步目的是减少每一行的权重，从而简化问题。

• 对每一行 i，计算 minRow = min(cost[i])，然后更新 cost[i][j] = cost[i][j] - minRow。

3. 列减法

对每一列，找到该列的最小元素，然后从该列的每个元素中减去这个最小值。这一步目的是为了进一步简化问题。

• 对每一列 j，计算 minCol = min(cost[i][j])，然后更新 cost[i][j] = cost[i][j] - minCol。

4. 标记行和列

对于这个矩阵，用数量最小的直线覆盖所有的0元素，如果线段数量为矩阵的列，那么，就找到了这样的最优分配。否则，找到没有被直线覆盖的元素中的最小的一个值，让每个没有完全被直线覆盖的元素行中的元素-这个值，让每个完全被直线覆盖了的列的元素+这个值。然后重复执行步骤3

算法时间复杂度

匈牙利算法的时间复杂度为O(n^3)，其中 n 是二分图中节点的个数（假设左右两部分的节点数相等）。