KM 算法

一、直观理解：一对一分配，不只求能配，还要求权之和最大

Kuhn–Munkres（KM）算法解决二分图最大权完美匹配（分配问题）：

$n$ 个工人、$n$ 个任务，工人 $i$ 做任务 $j$ 的收益为 $w_{ij}$，求一对一分配使总收益最大。

与无权匈牙利的区别：边带权，目标是权值和最优，而不是仅仅匹配边数最多。

对偶思想（顶标）：给每个左点 $u$ 顶标 $lx(u)$、右点 $v$ 顶标 $ly(v)$，始终保持

$$lx(u)+ly(v)\ge w(u,v)$$

在相等子图（使等号成立的边）上找完美匹配；若找不到，就按增广失败时的最小松弛量调整顶标，扩大相等子图，直到存在完美匹配。此时匹配权=顶标和，达到最优。

二、适用场景与优缺点

类型	说明
适用场景	指派问题；最大权/最小权一对一分配；资源—任务收益矩阵已知。
核心优点	多项式时间精确最优；有对偶证明；比盲目枚举 $n!$ 可行。
局限与缺点	通常要求两边等基数完美匹配（不足可补零）；实现细节多；稀疏极大图可用费用流更通用；最小权需权变号。

三、核心原理

1. 可行性顶标

满足 $lx(u)+ly(v)\ge w_{uv}$ 的顶标可行。对任意完美匹配 $M$，

$$\sum w(e)\le \sum_u lx(u)+\sum_v ly(v)$$

若 $M$ 全在相等子图中，则等号成立，故最优。

2. 算法步骤（概要）

1. 初始化：$lx(u)=\max_v w_{uv}$，$ly=0$；
2. 对每个左点，在相等子图中 DFS/BFS 找增广路；
3. 失败则计算松弛

$$\Delta=\min_{u\in S,v\notin T}\{lx(u)+ly(v)-w_{uv}\}$$

更新 $lx$ 减 $\Delta$、$ly$ 加 $\Delta$； 4. 直到所有左点匹配。

3. 最小权分配

令 $w'=-w$ 做最大权，或把顶标不等式方向按实现调整。

4. 与匈牙利、费用流

KM 是带权匈牙利；也可用最小费用最大流在完备二分图上求。

四、关键决策

1. 矩阵是否方阵

人多任务少或反之：补虚拟节点，权为 0 或足够差。

2. 不可行边

权设为极大负（最大权）或断边。

3. 数值

权尽量整数；浮点注意 $\varepsilon$ 比较。

4. 验证

检查是否一对一；与随机交换的局部改进比较；小 $n$ 可与枚举/ matchpairs 对照。

五、MATLAB 示例

% 使用 matchpairs 求最小权匹配（Statistics/MATLAB 内置）
Wcost = [
    4 1 3
    2 0 5
    3 2 2
];
% matchpairs 解最小权：列任务、行工人
M = matchpairs(Wcost, 1e6);
disp("匹配 (行,列):"); disp(M);
totalCost = 0;
for k = 1:size(M,1)
    totalCost = totalCost + Wcost(M(k,1), M(k,2));
end
fprintf("最小总费用=%g\n", totalCost);

% 最大权：对权取负
Wben = [
    9 6 7
    5 8 4
    7 6 10
];
M2 = matchpairs(-Wben, 1e6);
totalBen = 0;
for k = 1:size(M2,1)
    totalBen = totalBen + Wben(M2(k,1), M2(k,2));
end
fprintf("最大总收益=%g\n", totalBen);

% ---- 教学版 KM（最大权，n 小）----
w = Wben; n = size(w,1);
lx = max(w, [], 2)'; ly = zeros(1,n);
matchR = zeros(1,n); % 右点匹配的左点

for s = 1:n
    % slack 等
    while true
        visL = false(1,n); visR = false(1,n);
        slack = inf(1,n); slackY = zeros(1,n);
        % DFS
        function ok = dfs(u)
            visL(u) = true;
            for v = 1:n
                if visR(v), continue; end
                gap = lx(u)+ly(v)-w(u,v);
                if abs(gap) < 1e-9
                    visR(v) = true;
                    if matchR(v)==0 || dfs(matchR(v))
                        matchR(v)=u; ok=true; return;
                    end
                elseif slack(v) > gap
                    slack(v)=gap; slackY(v)=u;
                end
            end
            ok=false;
        end
        if dfs(s)
            break;
        end
        % 更新顶标
        delta = min(slack(~visR));
        if isempty(delta) || isinf(delta)
            error("无完美匹配");
        end
        for u = 1:n
            if visL(u), lx(u)=lx(u)-delta; end
        end
        for v = 1:n
            if visR(v)
                ly(v)=ly(v)+delta;
            else
                slack(v)=slack(v)-delta;
            end
        end
    end
end
assign = zeros(1,n);
for v = 1:n
    assign(matchR(v)) = v;
end
fprintf("KM 分配: 工人i->任务 "); disp(assign);
val = 0;
for u = 1:n, val = val + w(u, assign(u)); end
fprintf("KM 最大权=%g\n", val);

说明：内置 matchpairs 更稳妥；手写 KM 便于理解顶标更新。若运行环境对嵌套函数作用域严格，可将 DFS 改写为显式栈。

六、如何解释结果

1. 收益/成本矩阵含义与单位；
2. 最大权还是最小权；
3. 分配表与目标值；
4. 虚拟节点如何处理；
5. 与贪心按最大元取法的对照；
6. 灵敏度：某 $w_{ij}$ 变化是否改分配。

七、常见误区

1. 每行取最大元素

全局可能冲突，非最优。

2. 矩阵非方不处理

需补点。

3. 最小/最大目标搞反

符号错误。

4. 把 KM 用于非一对一容量

应改费用流。

八、小结

KM 算法的核心是：

维护可行顶标，在相等子图上求完美匹配，并通过调整顶标扩展相等子图，直至得到最大权完美匹配。

它是带权分配的经典精确算法。建模中写清权的业务含义，并用 matchpairs 或费用流做交叉验证，结果更可靠。