匈牙利算法

匈牙利算法用顶点势给每个任务和工人分摊“基础价格”，把指派成本变成非负约化成本，并只在成本恰好等于两端价格和的“紧边”所组成的相等子图中寻找增广匹配。若当前相等子图无法继续增广，就调整势，在保持对偶可行的同时让至少一条新边变紧，逐步暴露候选边；匹配大小与对偶目标同步推进。它是原始—对偶思想的具体实现，而不只是某种矩阵行列减法技巧。

三名工人与三项任务构成 $3\times 3$ 成本矩阵，算法最终选每行每列恰一个元素。矩形矩阵可补虚拟顶点和零/适当成本化为方阵。匈牙利算法求的是带权二分匹配，不是一般图带权匹配；也不能简单用逐行最便宜任务，因为会产生列冲突。势更新必须保持所有对偶约束可行，紧边上的完美匹配与对偶目标相等时由强对偶证明最优。

对成本矩阵，给每行、列维护势 $u_i,v_j$，要求 $u_i+v_j\le c_{ij}$；约化成本为 $c_{ij}-u_i-v_j\ge 0$。找到全匹配且所有匹配边紧时，原始匹配成本等于对偶势和，由弱对偶知已最优。

最小化与最大化版本的符号和初始化不同，直接复制公式容易反向。非方阵可补虚拟行列，但虚拟边成本需表达“未指派”语义；算法处理的是二分图指派，不是一般图最大匹配的同名历史算法混用。

指派问题出现在任务调度、数据关联、最优配对和多目标跟踪；匈牙利算法也是原始—对偶方法的经典实例。

二分匹配公理库匹配Matching in a graph由彼此不共享端点的边组成、表达一对一配对约束的边集合。 是原始解，线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。 与对偶势解释最优性，成本矩阵公理库矩阵Matrix以有限行列集合为索引、取值于半环，并以中间指标求和定义乘法的函数。 给出稠密输入。任务分配、最小权完美匹配和多目标关联都可归约到指派问题。

Hungarian algorithm解决二分图完美匹配/指派的加权特例，依顶点势与增广结构。拟阵交算法公理库拟阵交算法Matroid intersection algorithm · Unweighted matroid intersection在两个有限拟阵的交换有向图中寻找最短增广路，以独立性 oracle 构造最大公共独立集并在无路时输出秩和证书。把“同时独立于两个拟阵”作为更一般接口，二分匹配可编码为两个分割拟阵的交；这并不让 Hungarian 的势更新直接推广到一般拟阵 oracle，后者使用交换图并有独立查询成本。