二分图最大权完美匹配的 Kuhn-Munkres 算法（匈牙利算法扩展）

题目描述

我们有一个完全二分图，其中左侧顶点集为 \(X = \{x_1, x_2, \dots, x_n\}\)，右侧顶点集为 \(Y = \{y_1, y_2, \dots, y_n\}\)。每条边 \((x_i, y_j)\) 都有一个权重 \(w_{ij}\)。目标是找到一个完美匹配（即每个顶点恰好被匹配一次），使得匹配中所有边的权重之和最大（或最小）。这个问题称为二分图最大权完美匹配（Assignment Problem）。

Kuhn-Munkres 算法（也称为匈牙利算法）是解决该问题的经典算法，时间复杂度为 \(O(n^3)\)。下面以最大权为例讲解，最小权可以通过对所有权重取反转化为最大权问题。

解题过程循序渐进讲解

1. 核心思想：转化为等价标号问题

直接搜索所有完美匹配的代价太高（\(n!\)）。KM 算法的核心是引入顶点标号（label）的概念。

• 对每个左侧顶点 \(x_i\)，赋予一个标号 \(lx[i]\)。
• 对每个右侧顶点 \(y_j\)，赋予一个标号 \(ly[j]\)。
• 这些标号需要满足对于所有边 \((i, j)\) 的 可行性条件：\(lx[i] + ly[j] \geq w_{ij}\)。
• 定义相等子图 \(G_l\)：只包含满足 \(lx[i] + ly[j] = w_{ij}\) 的边 \((i, j)\) 的子图。

关键定理：如果在某个可行标号 \((lx, ly)\) 下，相等子图 \(G_l\) 中存在一个完美匹配 \(M\)，那么 \(M\) 就是原图的一个最大权完美匹配，且其权重和等于所有顶点标号之和，即 \(\sum lx[i] + \sum ly[j]\)。

直观理解：可行性条件保证了任何匹配的权重和都不会超过总标号和。而相等子图中的完美匹配恰好达到了这个上界，因此它是最优的。

2. 算法框架

KM 算法是一个增量构造完美匹配的过程，同时不断调整标号以扩大相等子图，直至找到完美匹配。

1. 初始化可行顶标：设定一个初始的可行标号。一个简单且有效的初始化是：
   • 对于左侧顶点 \(i\)：\(lx[i] = \max_{j} w_{ij}\)（即第 \(i\) 行的最大值）。
   • 对于右侧顶点 \(j\)：\(ly[j] = 0\)。
   • 这显然满足可行性条件 \(lx[i] + ly[j] \geq w_{ij}\)。
2. 尝试在相等子图中寻找完美匹配：使用类似匈牙利算法（寻找最大匹配）的方法，为每个左侧顶点 \(x_i\) 寻找匹配。但在 KM 中，我们只在相等子图 \(G_l\) 中进行增广。
3. 如果找到完美匹配：算法结束，当前匹配即为答案。
4. 如果未找到完美匹配：说明当前相等子图不够“丰富”，无法容纳一个完美匹配。这时，我们需要调整顶标，向相等子图中添加新的边，同时保持可行性条件。
   • 设我们在为左侧顶点 \(u\) 寻找匹配时失败。
   • 令 \(S\) 为本次搜索中访问过的左侧顶点集合（包含 \(u\)），\(T\) 为访问过的右侧顶点集合。
   • 在相等子图中，所有从 \(S\) 出发的边都指向 \(T\)（这是匈牙利算法 DFS/BFS 搜索的性质）。
   • 我们需要添加一些从 \(S\) 到 \(Y \setminus T\)（未访问右侧顶点）的边到相等子图中。
   • 计算标号调整量 \(\delta\)：

\[ \delta = \min_{i \in S, j \notin T} \{ lx[i] + ly[j] - w_{ij} \} \]

    $ \delta $ 是所有从 $ S $ 到 $ Y \setminus T $ 的边中，与“相等”条件差距最小的值，且 $ \delta > 0 $。
*   **调整标号**：
    *   对所有 $ i \in S $：$ lx[i] := lx[i] - \delta $。
    *   对所有 $ j \in T $：$ ly[j] := ly[j] + \delta $。
*   **调整的影响**：
    *   对于 $ S $ 和 $ T $ 之间的边：$ lx[i] + ly[j] $ 不变（$ -\delta + +\delta $），它们仍然在相等子图中。
    *   对于 $ S $ 和 $ Y \setminus T $ 之间的边：其中差距正好为 $ \delta $ 的那条（或多条）边的两端标号和将等于权重，被**添加**到相等子图中。
    *   对于 $ X \setminus S $ 和 $ T $ 之间的边：$ lx[i] + ly[j] $ 增加（因为 $ ly[j] $ 增加了），它们可能**离开**相等子图，但这无关紧要，因为我们的搜索尚未用到它们。
    *   对于其他边：可行性条件保持或变得更易满足。

5. 调整标号后，保持当前已找到的匹配（它们仍在相等子图中），然后从失败的左侧顶点 \(u\) 开始，继续尝试增广（因为新的边被加入了相等子图）。
6. 重复步骤 2-5，直到为所有左侧顶点找到匹配。

3. 详细步骤示例（基于 DFS 的实现）

假设我们有一个 3x3 的权重矩阵，求最大权完美匹配：

\[W = \begin{bmatrix} 3 & 5 & 4 \\ 2 & 1 & 3 \\ 4 & 2 & 5 \end{bmatrix} \]

Step 1: 初始化

• \(lx = [5, 3, 5]\)（每行最大值）
• \(ly = [0, 0, 0]\)
• 相等子图包含边：满足 \(w_{ij} = lx[i]\) 的边。即 (x1, y2:5), (x2, y3:3), (x3, y1:4? 这里注意 w31=4≠lx[3]=5，所以初始相等子图边是 (x3, y3:5)）。更准确地说，初始相等子图是满足 \(w_{ij} = lx[i]\) 的边，因为 ly[j]=0。所以：
  • x1: 边权为5的只有 y2。所以边 (1,2)。
  • x2: 边权为3的只有 y3。所以边 (2,3)。
  • x3: 边权为5的只有 y3。所以边 (3,3)。
• 初始匹配 \(M = \emptyset\)。

Step 2: 为 x1 寻找增广路
在相等子图中从 x1 出发，它只有一条边 (1,2)。y2 未被匹配，所以直接匹配 (1,2)。\(M = \{(1,2)\}\)。

Step 3: 为 x2 寻找增广路
从 x2 出发，它只有边 (2,3)。y3 未被匹配，直接匹配 (2,3)。\(M = \{(1,2), (2,3)\}\)。

Step 4: 为 x3 寻找增广路
从 x3 出发，它只有边 (3,3)。但 y3 已被 x2 匹配。

• 我们尝试“腾挪”：查看 x2（匹配了 y3 的点）是否有其他选择。
• 从 x2 出发，在相等子图中它只有边 (2,3)，而 y3 正是当前冲突点，没有其他边。
• 增广失败。此时：
  • \(S = \{x3, x2\}\)（DFS 访问的左侧点）。
  • \(T = \{y3\}\)（访问的右侧点）。
• 计算调整量 \(\delta\)：
  • 考虑边 \((i, j)\) 其中 \(i \in S\), \(j \notin T\)（即 j = y1 或 y2）。
  • (3,1): \(lx[3]+ly[1]-w_{31} = 5+0-4 = 1\)
  • (3,2): \(5+0-2 = 3\)
  • (2,1): \(3+0-2 = 1\)
  • (2,2): \(3+0-1 = 2\)
  • \(\delta = \min(1,3,1,2) = 1\)。
• 调整标号：
  • \(S\) 中顶点：\(lx[2]=3-1=2\), \(lx[3]=5-1=4\)。
  • \(T\) 中顶点：\(ly[3]=0+1=1\)。
  • 新标号：\(lx = [5, 2, 4]\), \(ly = [0, 0, 1]\)。
• 更新相等子图（重新计算满足 \(lx[i]+ly[j]==w_{ij}\) 的边）：
  • x1: (1,2:5) 满足 5+0=5。
  • x2: 原来(2,3:3) 现在 2+1=3，满足。新增 (2,1:2) 满足 2+0=2。
  • x3: 原来(3,3:5) 现在 4+1=5，满足。新增 (3,1:4) 满足 4+0=4。
• 保持现有匹配 \(M = \{(1,2), (2,3)\}\)。

Step 5: 继续为 x3 寻找增广路（重新尝试）
从 x3 出发，在新的相等子图中，它的邻点有 y1 和 y3。

• 尝试 y1：y1 未被匹配！成功找到一条增广路 x3 -> y1。
• 匹配 (3,1)。现在 \(M = \{(1,2), (2,3), (3,1)\}\)，已形成完美匹配。

Step 6: 计算权重和
匹配边： (1,2):5, (2,3):3, (3,1):4。总和 = 12。
检查标号和：\(lx\) 总和 = 5+2+4=11，\(ly\) 总和 = 0+0+1=1，总标号 = 12，等于匹配权重和，验证了定理。

4. 算法实现细节（\(O(n^3)\) 的经典写法）

通常使用一个 \(n \times n\) 的权重矩阵 w[][]，以及数组 lx[], ly[], matchY[]（记录右侧点匹配的左侧点），slack[]（用于优化调整量计算）。

def km(n, w):
    lx = [max(row) for row in w] # 初始lx
    ly = [0] * n
    matchY = [-1] * n # 右侧点匹配的左侧点索引，-1表示未匹配
    pre = [-1] * n # 用于记录增广路径

    for u in range(n): # 尝试为每个左侧点u找匹配
        # 初始化
        visX = [False] * n
        visY = [False] * n
        slack = [float('inf')] * n
        # 从u开始寻找增广路
        v = -1
        matchY[v] = u # 虚拟起点
        while True:
            u = matchY[v] # 当前要处理的左侧点
            visX[u] = True
            d = float('inf')
            minV = -1
            # 更新slack并找到最小的调整量
            for j in range(n):
                if not visY[j]:
                    diff = lx[u] + ly[j] - w[u][j]
                    if diff < slack[j]:
                        slack[j] = diff
                        pre[j] = v # 记录路径
                    if slack[j] < d:
                        d = slack[j]
                        minV = j
            # 调整标号
            for i in range(n):
                if visX[i]:
                    lx[i] -= d
            for j in range(n):
                if visY[j]:
                    ly[j] += d
                else:
                    slack[j] -= d # 所有slack值也同步减少d
            v = minV
            if matchY[v] == -1: # 找到未匹配的右侧点，增广成功
                break
            visY[v] = True
        # 回溯更新匹配
        while v != -1:
            matchY[v] = matchY[pre[v]]
            v = pre[v]

    # 计算最大权值和
    total = 0
    for j in range(n):
        i = matchY[j]
        total += w[i][j]
    return total, matchY

5. 总结

Kuhn-Munkres 算法通过巧妙的顶点标号系统，将最大权匹配问题转化为在等价子图中寻找完美匹配的问题。通过迭代调整标号，逐步扩大等价子图，最终得到最优解。其 \(O(n^3)\) 的复杂度对于许多实际问题（\(n\) 在几百到几千）是可行的，是解决指派类问题的标准算法。