匈牙利指派法

匈牙利算法（Hungarian Algorithm）是求解指派问题的经典算法，用于在 n×nn×n 的代价矩阵中，找到一组不同行、不同列的分配方案，使总代价最小。你总结的四个步骤抓住了核心，下面把它讲透，并补充原理、证明和工程实现。一、问题模型有 nn 个任务和 nn 个人，每个人完成每个任务的代价不同，要求一人一任务，如何分配使总代价最小。代价矩阵：C=[c11c12⋯c1nc21c22⋯c2n⋮⋮⋱⋮cn1cn2⋯cnn]C=​c11​c21​⋮cn1​​c12​c22​⋮cn2​​⋯⋯⋱⋯​c1n​c2n​⋮cnn​​​目标：找到排列 σσ，使 ∑i=1nci,σ(i)∑i=1n​ci,σ(i)​ 最小。二、核心定理定理：如果对代价矩阵的某一行（或某一列）所有元素同时加上或减去一个常数 kk，最优指派方案不变。证明：任何方案都会且仅会从该行取一个元素，减去 kk 后，该方案的总代价减少 kk，所有方案减少量相同，所以最优方案不变。这个定理是匈牙利算法所有变换的基础。三、算法步骤详解步骤 1：行变换对每一行，减去该行的最小值。text例： [ 4 8 6 ] [ 0 4 2 ] [ 6 10 4 ] → [ 2 6 0 ] [ 8 6 10 ] [ 2 0 4 ]每行至少出现一个 0。如果某行只有一个 0，称该 0 为行独立 0，可以画掉该 0 所在的列。步骤 2：列变换对每一列，减去该列的最小值。text[ 0 4 2 ] [ 0 4 0 ] [ 2 6 0 ] → [ 2 6 0 ]