匈牙利算法详解（Java语言实现任务分配与二分图最大匹配）

什么是任务分配问题？

假设你有 n 个工人和 n 个任务，每个工人完成每个任务的成本不同。目标是为每个工人分配一个唯一的任务，使得总成本最小。这就是典型的任务分配问题。

例如：

• 工人 A 完成任务 1 成本为 9，任务 2 成本为 2
• 工人 B 完成任务 1 成本为 6，任务 2 成本为 4

显然，让 A 做任务 2（成本 2），B 做任务 1（成本 6），总成本为 8，是最优解。

匈牙利算法的核心思想

匈牙利算法基于二分图最大匹配理论，通过以下步骤求解：

1. 行约简：每行减去该行最小值
2. 列约简：每列减去该列最小值
3. 覆盖所有零的最少直线数：若直线数等于矩阵阶数 n，则存在最优分配；否则调整矩阵继续
4. 调整矩阵：找出未被覆盖的最小元素，进行加减操作，重复步骤 3

Java 实现匈牙利算法

下面是一个完整的 Java 实现，包含详细注释：

import java.util.Arrays;public class HungarianAlgorithm {    private int[][] costMatrix;    private int n;    private boolean[] rowCovered;    private boolean[] colCovered;    private int[][] marked; // 0: unmarked, 1: starred zero, 2: primed zero    public HungarianAlgorithm(int[][] matrix) {        this.n = matrix.length;        this.costMatrix = new int[n][n];        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                this.costMatrix[i][j] = matrix[i][j];            }        }        this.rowCovered = new boolean[n];        this.colCovered = new boolean[n];        this.marked = new int[n][n];    }    public int[] solve() {        // Step 1: 行约简        for (int i = 0; i < n; i++) {            int min = Arrays.stream(costMatrix[i]).min().orElse(0);            for (int j = 0; j < n; j++) {                costMatrix[i][j] -= min;            }        }        // Step 2: 列约简        for (int j = 0; j < n; j++) {            int min = Integer.MAX_VALUE;            for (int i = 0; i < n; i++) {                if (costMatrix[i][j] < min) min = costMatrix[i][j];            }            for (int i = 0; i < n; i++) {                costMatrix[i][j] -= min;            }        }        // 初始化标记        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (costMatrix[i][j] == 0 && !rowCovered[i] && !colCovered[j]) {                    marked[i][j] = 1; // starred zero                    rowCovered[i] = true;                    colCovered[j] = true;                }            }        }        Arrays.fill(rowCovered, false);        Arrays.fill(colCovered, false);        // Step 3: 检查是否完成        while (true) {            int coveredCols = 0;            for (int j = 0; j < n; j++) {                for (int i = 0; i < n; i++) {                    if (marked[i][j] == 1) {                        colCovered[j] = true;                        coveredCols++;                        break;                    }                }            }            if (coveredCols == n) {                break; // 找到最优解            }            // Step 4-6: 覆盖零、调整矩阵（简化版，完整实现较复杂）            // 此处为教学目的简化，实际项目建议使用成熟库如 Apache Commons Math            // 完整实现涉及路径构造等，篇幅所限略去            // 返回当前最优分配（仅适用于已覆盖全部列的情况）            break;        }        // 构造结果        int[] result = new int[n];        for (int j = 0; j < n; j++) {            for (int i = 0; i < n; i++) {                if (marked[i][j] == 1) {                    result[i] = j;                    break;                }            }        }        return result;    }    public static void main(String[] args) {        int[][] cost = {            {9, 2},            {6, 4}        };        HungarianAlgorithm ha = new HungarianAlgorithm(cost);        int[] assignment = ha.solve();        System.out.println("分配结果：");        for (int i = 0; i < assignment.length; i++) {            System.out.println("工人 " + i + " → 任务 " + assignment[i]);        }    }}

注意：上述代码为教学简化版，完整匈牙利算法实现较为复杂，涉及“增广路径”构造。生产环境中建议使用 Apache Commons Math 等成熟库。

应用场景

匈牙利算法不仅用于任务分配，还可用于：

• 多目标跟踪中的数据关联
• 图像特征点匹配
• 考试监考人员排班
• 物流配送路径优化

总结

通过本教程，你已经了解了匈牙利算法的基本原理，并学会了如何用 Java语言实现匈牙利算法来解决任务分配问题。虽然完整实现较为复杂，但掌握其核心思想——基于二分图最大匹配的优化策略——对你理解组合优化问题大有裨益。

建议初学者先理解算法逻辑，再尝试编码。后续可深入学习 Kuhn-Munkres 算法（即匈牙利算法的扩展版本）以处理非方阵情况。

动手实践是掌握算法的最佳方式！快用 Java 写一个自己的匈牙利算法吧！