4. 匈牙利算法详解：指派问题与匈牙利算法、算法步骤与复杂度分析、Python实现与可视化

4.1 从指派问题说起

先聊聊指派问题。说白了，就是有 N 个任务和 N 个人，每个人做每个任务的成本不一样，怎么分配才能让总成本最低？

我当年在安防项目里就遇到过。有 8 个摄像头检测到的目标，要分配给 8 个跟踪器。每个匹配都有一个代价——比如位置距离、外观相似度。这不就是个典型的指派问题嘛。

数学上，我们这样描述：

• 有 N 个任务和 N 个工人
• 成本矩阵 C，其中 C[i][j] 表示工人 i 做任务 j 的成本
• 目标是找到一个排列 π，使得 ∑C[i][π(i)] 最小

你想想看，暴力枚举要 N! 种可能。N=10 时就是 362 万种，N=20 时直接爆炸。所以我们需要更聪明的办法。

4.2 匈牙利算法的核心思想

匈牙利算法，也叫 Kuhn-Munkres 算法。它基于一个很巧妙的观察：

为什么会这样？因为每个工人恰好做一个任务，每个任务恰好被一个工人做。行或列减去常数，相当于所有分配方案都减去了同一个值，不影响相对大小。

基于这个定理，算法反复做两件事：

1. 化简矩阵：每行减最小值，每列减最小值
2. 覆盖零元素：用最少的直线覆盖所有零

当覆盖所有零需要 N 条直线时，我们就找到了最优解。

4.3 算法步骤详解

嗯，这里我直接给出标准步骤，配合一个例子来讲。

假设我们有 3 个工人和 3 个任务，成本矩阵如下：

	任务1	任务2	任务3
工人A	4	1	3
工人B	2	0	5
工人C	3	2	2

步骤1：行化简

每行减去该行最小值。第一行减1，第二行减0，第三行减2：

	任务1	任务2	任务3
工人A	3	0	2
工人B	2	0	5
工人C	1	0	0

步骤2：列化简

每列减去该列最小值。第一列减1，第二列减0，第三列减0：

	任务1	任务2	任务3
工人A	2	0	2
工人B	1	0	5
工人C	0	0	0

步骤3：用最少直线覆盖所有零

这里需要画 2 条线（比如第二列和第三行）。2 < 3，所以还没到最优。

步骤4：调整矩阵

找到未被覆盖的最小值（这里是 1）。所有未被覆盖的元素减 1，被两条线交叉的元素加 1：

	任务1	任务2	任务3
工人A	1	0	1
工人B	0	0	4
工人C	0	1	0

现在需要 3 条线才能覆盖所有零。找到最优分配：A→任务2，B→任务1，C→任务3。总成本 = 1 + 2 + 2 = 5。

4.4 复杂度分析

匈牙利算法的时间复杂度是 O(N³)。为什么？

• 每次迭代需要 O(N²) 来寻找未被覆盖的最小值
• 最多迭代 O(N) 次
• 所以总复杂度 O(N³)

空间复杂度是 O(N²)，主要存储成本矩阵。

说实话，O(N³) 在目标关联场景下完全够用。一般跟踪目标也就几十个，N=50 时 50³=125000，毫秒级就能算完。

4.5 Python 实现

我直接给出一个简洁的实现。这个版本我用了很多次，稳定可靠。

import numpy as np
from scipy.optimize import linear_sum_assignment

def hungarian_algorithm(cost_matrix):
    """
    匈牙利算法求解指派问题
    
    参数:
        cost_matrix: np.ndarray, 形状 (N, N)
    
    返回:
        row_ind, col_ind: 最优分配的行索引和列索引
    """
    # 直接用 scipy 的封装，底层是 C++ 实现
    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    return row_ind, col_ind

# 手动实现版本（教学用）
def hungarian_manual(cost):
    n = cost.shape[0]
    # 复制矩阵，避免修改原数据
    u = cost.copy()
    
    # 行化简
    u = u - u.min(axis=1, keepdims=True)
    # 列化简
    u = u - u.min(axis=0, keepdims=True)
    
    # 标记哪些行和列被覆盖
    covered_rows = np.zeros(n, dtype=bool)
    covered_cols = np.zeros(n, dtype=bool)
    
    # 这里省略了完整的增广路径实现
    # 实际项目中建议直接用 scipy
    
    return linear_sum_assignment(cost)

# 使用示例
if __name__ == "__main__":
    # 成本矩阵
    cost = np.array([
        [4, 1, 3],
        [2, 0, 5],
        [3, 2, 2]
    ])
    
    row_ind, col_ind = hungarian_algorithm(cost)
    
    print("最优分配：")
    for i, j in zip(row_ind, col_ind):
        print(f"工人 {i} → 任务 {j}, 成本 {cost[i][j]}")
    print(f"总成本: {cost[row_ind, col_ind].sum()}")

4.6 可视化展示

下面我用 SVG 画一个匈牙利算法的流程图，帮你理清整个逻辑。

4.7 实际应用中的注意事项

最后，分享几个实战经验：

• 成本矩阵要对称：如果工人数和任务数不等，可以补虚拟行/列，成本设为大数
• 最大化问题：取负号或取倒数，转化为最小化问题
• 数值稳定性：成本值不要太大，否则浮点误差会累积。我习惯归一化到 [0, 1] 区间
• 实时性要求：如果目标超过 100 个，考虑用贪心近似算法，匈牙利算法会有点慢

可可精品资料库