헝가리안 알고리즘

할당 문제의 O(N³) 최적 매칭.

다이아몬드 I

1강 할당 문제와 헝가리안 알고리즘 공식

문제

$n\times n$ 비용 행렬 $c_{ij}$ ( $$i$$ 번 일꾼을 $$j$$ 번 일에 배정하는 비용)에서, 각 일꾼이 서로 다른 일 하나씩을 맡는 완전 매칭 중 총비용을 최소화하는 배정을 찾는다. 이분 그래프의 최소 가중 완전 매칭이며, 헝가리안(쿤-멍크레스) 알고리즘이 $$O(n^3)$$ 에 푼다.

쌍대성과 potential

선형계획 쌍대를 도입한다. 각 행 $$i$$ 에 잠재값 $$u_i$$ , 각 열 $$j$$ 에 $$v_j$$ 를 두고 항상

$u_i + v_j \le c_{ij}$

를 유지한다(쌍대 실현가능). reduced cost $c_{ij} - u_i - v_j \ge 0$ 이 0인 간선(tight edge)만으로 완전 매칭이 구성되면, 상보여유정리에 의해 그 매칭이 최적이다. 알고리즘은 잠재값을 조금씩 올리며 tight edge를 늘려, 마침내 완전 매칭을 만든다.

증대 경로(augmenting path)

현재 tight edge 그래프에서 매칭되지 않은 행을 출발점으로 교대 경로를 찾는다. 매칭에 새 행을 추가할 증대 경로를 못 찾으면, 도달 가능한 행/열 집합으로 잠재값을 조정한다:

$\Delta = \min_{\substack{i \in S,\ j \notin T}} (c_{ij} - u_i - v_j),\qquad u_i \mathrel{+}= \Delta\ (i\in S),\quad v_j \mathrel{-}= \Delta\ (j\in T).$

이 조정으로 적어도 하나의 새 tight edge가 생겨 탐색 트리가 확장된다. 각 행을 매칭에 넣을 때마다 $$O(n)$$ 번의 잠재값 조정, 조정마다 $$O(n)$$ 작업 → 행당 $$O(n^2)$$ , 전체 $$O(n^3)$$ .

정확성

알고리즘 종료 시 모든 행이 매칭되고 모든 간선이 $u_i+v_j\le c_{ij}$ , 매칭 간선은 등호를 만족한다. 임의의 실현가능 매칭 $$M'$$ 에 대해

$\sum_{(i,j)\in M'} c_{ij} \ge \sum_i u_i + \sum_j v_j = \sum_{(i,j)\in M} c_{ij}$

이므로 $$M$$ 이 최소. (약쌍대성에서 등호 달성.)

복잡도와 변형

항목	값
시간	$$O(n^3)$$
직사각( $n\le m$ )	$O(n^2\ m)$
최대화	비용 부호 반전 또는 $C-c_{ij}$

2강 헝가리안 $O(n^3)$ 구현과 응용 공식

표준 구현 (1-indexed, 최소 비용)

널리 쓰이는 $$O(n^3)$$ 잠재값 갱신형. 행 $$n$$ , 열 $$m$$ ( $n\le m$ ).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

// cost[1..n][1..m], 반환: 최소 총비용. assign[j] = 열 j에 매칭된 행.
ll hungarian(int n, int m, vector<vector<ll>>& cost, vector<int>& assignByCol) {
    vector<ll> u(n + 1, 0), v(m + 1, 0);
    vector<int> p(m + 1, 0), way(m + 1, 0);     // p[j]: 열 j에 매칭된 행
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<ll> minv(m + 1, INF);
        vector<bool> used(m + 1, false);
        do {                                    // 증대 경로 탐색
            used[j0] = true;
            int i0 = p[j0], j1 = -1;
            ll delta = INF;
            for (int j = 1; j <= m; j++) if (!used[j]) {
                ll cur = cost[i0][j] - u[i0] - v[j];
                if (cur < minv[j]) { minv[j] = cur; way[j] = j0; }
                if (minv[j] < delta) { delta = minv[j]; j1 = j; }
            }
            for (int j = 0; j <= m; j++) {       // 잠재값 갱신
                if (used[j]) { u[p[j]] += delta; v[j] -= delta; }
                else minv[j] -= delta;
            }
            j0 = j1;
        } while (p[j0] != 0);
        do { int j1 = way[j0]; p[j0] = p[j1]; j0 = j1; } while (j0); // 증대
    }
    assignByCol = p;
    ll res = 0;
    for (int j = 1; j <= m; j++) if (p[j]) res += cost[p[j]][j];
    return res;
}

자주 하는 실수

1-indexed 가정. 위 구현은 p[0]/minv[0] 보초를 쓴다. 0-index로 옮기면 보초 처리를 다시 설계해야 한다.
직사각 처리. $n\le m$ 이어야 한다. 행이 더 많으면 전치하거나 더미 열을 채운다.
최대화. 비용을 음수로 하거나 big - cost 로 변환. INF가 오버플로하지 않게 한다.
불가능 배정. 금지 간선은 매우 큰 비용으로. 단 INF끼리 더해 오버플로하지 않도록.

응용

문제	모델
작업-기계 최소비용 배정	그대로
최소 가중 완전 이분 매칭	비용 행렬
좌표 매칭(점-점 거리 합 최소)	거리 행렬
일부만 매칭(직사각)	더미 행/열

다른 매칭과의 관계

가중치 없는 최대 이분 매칭은 호프크로프트-카프( $O(E\sqrt V)$ )가 더 빠르다. 헝가리안은 가중치가 있는 완전 매칭에 특화된다. 일반(비이분) 가중 매칭은 블로섬 기반 알고리즘이 필요하다.

항목	값
시간	$\(O(n^3)\)$
직사각( $n\le m$ )	$O(n^2\ m)$
최대화	비용 부호 반전 또는 $C-c_{ij}$