匈牙利算法解决整体最优分配问题<未完成>发布于2024-09-01 23:27:14，更新于2024-11-11 22:11:53，标签：java 文章会持续修订，转载请注明来源地址：https://meethigher.top/blog

一、背景

1.1 应用场景

美真是铠甲勇士的指挥官，手下有五个铠甲勇士在闲着。正所谓养兵千日用兵一时，现在有突发预警，三个地方出现了异能兽。

现在美真需要立即安排三个铠甲勇士去现场解决异能兽，但要保证铠甲勇士们整体移动距离最少的情况下到达异能兽目的地。

已知铠甲到达异能兽位置的距离如下，

目的地/与铠甲距离	炎龙铠甲	风影铠甲	地虎铠甲	雪獒铠甲	黑犀铠甲
恶参兽	1	2	3	4	5
刺木兽	2	3	4	5	6
蚂蚱兽	3	4	5	6	7

1.2 解决思路

这个问题可以被看作是经典的“指派问题” (Assignment Problem)，其核心是如何最优分配任务，以使总距离最短。我们可以使用“匈牙利算法”（Hungarian Algorithm）来求解该问题。

下面需要一步步了解概念。

二、图

图是由“顶点”和“边”所组成的集合，通常用G=(V,E)来表示，其中V是所有顶点所组成的集合，而E代表所有边所组成的集合。

图的种类有两种

• 无向图。以(V1,V2)表示其边。
• 有向图。以<V1,V2>表示其边。

2.1 无向图

无向图的基础概念以书中的截图展示如下。

2.2 有向图

有向图的基础概念以书中的截图展示如下。

2.3 图的数据表示法

下面给出一个无向图的示例图片

可以有三种方式来进行表示该图

• 邻接矩阵
• 邻接表
• 边列表

邻接矩阵（Adjacency Matrix）

• 使用一个二维矩阵表示图，矩阵中的每个元素表示节点之间是否有边相连。
• 如果图有 n 个节点，则邻接矩阵是一个 n x n 的矩阵。
• 无向图：矩阵是对称的，A[i][j] = A[j][i]。
• 有向图：矩阵不一定对称，A[i][j] 表示从节点 i 到节点 j 的边。
• 如果有边相连，A[i][j] = 1，否则为 0（在加权图中，A[i][j] 可以是权重值）。

优点：查找某两点之间是否有边时非常快速。

缺点：空间复杂度高，需要 O(n^2) 的存储空间，尤其是稀疏图时非常浪费空间。

示例（以上述无向图为例）：

   A  B  C
A [0, 1, 1]
B [1, 0, 0]
C [1, 0, 0]

邻接表（Adjacency List）

• 使用一个列表数组，每个节点对应一个列表，列表中存储与该节点直接相连的其他节点。
• 对于无向图，节点 i 的列表中包含与 i 相连的所有节点；对于有向图，节点 i 的列表中只包含从 i 出发的节点。

优点：节省空间，特别适用于稀疏图；添加边和遍历相邻节点更高效。

缺点：查找两节点是否相邻时不如邻接矩阵高效。

示例（以上述无向图为例）：

A -> B, C
B -> A
C -> A

边列表（Edge List）

• 使用一个边的列表，每条边表示两个相连的节点和可能的边权。
• 每个元素表示一条边，例如 (A, B) 表示节点 A 和 B 相连，如果是加权图，可以表示为 (A, B, weight)。

优点：结构简单，适合表示稀疏图。

缺点：查找两节点是否相邻需要遍历整个边列表。

示例（以上述无向图为例）：

[(A, B), (A, C)]

适用场景：

• 邻接矩阵：适合边数多的图（密集图），因为查找某两点是否相连比较快。
• 邻接表：适合边数少的图（稀疏图），节省空间且遍历邻居高效。
• 边列表：适合简单图的表示或算法实现，特别是需要遍历所有边的情况。

这些表示方法根据不同场景和需求有各自的优缺点，具体选用哪种表示方法取决于图的规模、边的数量和使用场景。

三、经典匈牙利算法

3.1 二分图

一个图G=(V,E)，其中V是顶点集，E是边集。如果可以将顶点集V划分为两个不相交的集合V1和V2，并且满足图中的每条边都只连接V1和V2中的一个顶点。这种图G就叫做二分图。

3.2 最大匹配问题

实际场景：假设有一组男、女，每个人都有自己的偏好列表。最大匹配可以帮助找到尽可能多的婚姻组。

示例代码：

import java.util.Arrays;

public class HungarianAlgorithm {


    /**
     * 为二分图左侧集合中的顶点寻找一个右侧匹配
     * 该操作实际是为增广路径的概念提前铺垫一下
     *
     * @param graph  二分图
     * @param u      二分图左侧集合的顶点下标
     * @param matchR 二分图右侧集合匹配的左侧顶点下标
     * @param seen   二分图右侧集合中的顶点是否已被匹配
     * @return true表示成功寻到匹配，false表示未寻到
     */
    public static boolean bpm(int[][] graph, int u, int[] matchR, boolean[] seen) {
        // 尝试为左侧集合中的顶点 u 找到匹配
        for (int v = 0; v < graph[0].length; v++) {
            // 如果存在边，并且右侧顶点 v 还没有被访问过
            if (graph[u][v] == 1 && !seen[v]) {
                // 标记顶点 v 已经被访问
                seen[v] = true;
                // 如果右侧顶点 v 没有被匹配，或者之前匹配的左侧顶点可以找到其他匹配
                if (matchR[v] == -1 || bpm(graph, matchR[v], matchR, seen)) {
                    matchR[v] = u;  // 匹配左侧顶点 u 和右侧顶点 v
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 通过匈牙利算法计算最大匹配数量
     *
     * @param graph 二分图。使用邻接矩阵表示法
     * @return 最大匹配数量
     */
    public static int hungarianAlgorithm(int[][] graph) {
        int rowLength = graph.length;
        int colLength = graph[0].length;
        // 右侧集合顶点的匹配结果，初始化为 -1（表示未匹配）
        int[] matchR = new int[colLength];
        Arrays.fill(matchR, -1);

        // 结果变量，存储最大匹配数
        int result = 0;

        // 对于左侧集合中的每一个顶点，尝试找到一个匹配
        for (int u = 0; u < rowLength; u++) {
            // 初始化右侧集合中的顶点是否已被访问的数组
            boolean[] seen = new boolean[colLength];
            // 如果当前左侧顶点 u 能够找到匹配
            if (bpm(graph, u, matchR, seen)) {
                result++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 示例二分图的邻接矩阵表示
        // U = {u1, u2, u3}
        // V = {v1, v2, v3, v4}
        // 邻接矩阵 graph[i][j] 表示 U 中的顶点 i 和 V 中的顶点 j 之间是否有边
        int[][] graph = {
                {1, 0, 1, 0},  // u1 -> v1, v3
                {0, 1, 1, 0},  // u2 -> v2, v3
                {0, 0, 0, 1}   // u3 -> v4
        };

        // 运行匈牙利算法，获取最大匹配数
        System.out.println(hungarianAlgorithm(graph));


        // 测试用例
        int[][] t1 = {
                {1, 1, 0},   // u1->v1,v2
                {1, 0, 0},   // u2->v1
                {0, 0, 1},   // u3->v3
        };
        System.out.println(hungarianAlgorithm(t1));

        int[][] t2 = {
                {1, 1, 0},   // u1->v1,v2
                {1, 0, 0},   // u2->v1
                {1, 0, 0},   // u3->v1
        };
        System.out.println(hungarianAlgorithm(t2));
    }
}

五、解决背景问题

背景中的需求是要保证铠甲勇士们整体移动距离最少的情况下到达异能兽目的地。

这其实就是一个二分图最小权匹配问题，在这之前，需要先了解二分图最小权完美匹配的解法，即加权二分图中找出匹配的总权值最小的完美匹配。

增广路径：由一个未匹配顶点开始，经过若干个匹配顶点，最后到达对面集合的一个未匹配顶点的路径。即这条路径将两个不同集合的两个未匹配顶点通过一系列匹配顶点相连。

何为匹配顶点和未匹配顶点？以上图为例，假设当前的匹配为A->c,B->a，那么A、B、a、c就是匹配顶点，而b、C为未匹配顶点。

此时要找增广路径，根据其定义，只有一条：b->B->

5.1 二分图最小权匹配

5.2 二分图最小权完美匹配

匈牙利算法_增广路径取反是什么意思-CSDN博客

二分图前期基础之增广路忆恒心的技术博客_51CTO博客