헝가리안 알고리즘

최적설계 수치해석 마지막 수정: 2026-08-14 04:35:09

1. 개요[편집]

헝가리안 알고리즘 Hungarian Algorithm
다른 이름	쿤-먼크레스(Kuhn–Munkres) 알고리즘
발표	Harold Kuhn (1955) · James Munkres (1957)
푸는 문제	선형 할당 문제 (assignment problem)
복잡도	$O(n^3)$ (최단 증가경로 구현)
원리	원-쌍대법 — 쌍대변수 유지 + 등식 부분그래프 매칭
최적성 근거	상보 여유 조건 · 전체 단모듈성
실무 후계	JV(1987) · 경매 알고리즘(베르트세카스)

일꾼 $n$ 명과 작업 $n$ 개를 짝지어야 하는데 가능한 배정이 $n!$ 가지다. $n=20$ 이면 $2.4\times10^{18}$ 가지. 그런데 이 문제는 $8000$ 번의 연산이면 정확히 풀린다.

헝가리안 알고리즘(Hungarian algorithm)은 $n \times n$ 비용행렬이 주어졌을 때 행과 열을 일대일로 짝지어 총비용을 최소화하는 선형 할당 문제(assignment problem)를 다항시간에 정확히 푸는 원-쌍대(primal–dual) 알고리즘이다. 1955년 해럴드 쿤이 발표했고 1957년 제임스 먼크레스가 다항시간 보증을 명확히 정리해, 흔히 쿤-먼크레스 알고리즘이라 함께 부른다. 이름이 “헝가리안”인 것은 쿤이 알고리즘의 뼈대를 헝가리 수학자 쾨니그와 에게르바리의 결과에서 가져왔다고 밝히며 직접 붙인 헌사다.¹

이 문서는 할당 문제 전용 알고리즘의 내부 — 쌍대변수, 표 형태 절차, 최단 증가경로 구현, 그리고 실무 후계자들 — 을 다룬다. 매칭이라는 문제 자체의 조합론(베르주 정리, 홉크로프트-카프, 쾨니그 정리, 홀의 조건)은 이분 매칭에 정리돼 있고, 흐름 문제 일반은 네트워크 흐름이 담당한다.

2. 문제 정식화[편집]

비용 $c_{ij}$ 가 주어질 때 할당 문제는 다음 정수계획이다.

\min \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}x_{ij} \quad\text{s.t.}\quad \sum_j x_{ij} = 1\ \forall i,\quad \sum_i x_{ij} = 1\ \forall j,\quad x_{ij}\in\{0,1\}

여기서 놀라운 지점은 $x_{ij}\in\{0,1\}$ 을 $x_{ij}\ge 0$ 으로 풀어도 최적해가 여전히 0/1로 나온다는 것이다. 제약행렬이 이분 그래프의 접속행렬이라 전체 단모듈성을 만족하기 때문이며, 기하적으로는 이중확률행렬 다면체의 꼭짓점이 정확히 순열행렬이라는 버코프-폰 노이만 정리로 읽힌다. 즉 할당 문제는 선형계획법의 얼굴을 한 조합 문제이고, 그래서 정수계획법의 분지한정 없이 다항시간에 끝난다.

두 가지 사소하지만 실무에서 자주 걸리는 변형이 있다.

최대화 문제는 $c_{ij} \to M - c_{ij}$ ( $M$ 은 충분히 큰 상수)로 뒤집으면 그대로 최소화가 된다.
직사각 행렬( $n \times m$ , $n \le m$ )은 비용 0인 더미 행을 채워 정사각으로 만든다. “짝을 안 지어도 되는” 옵션이 필요하면 더미 열에 임계 비용을 넣는다 — 다중 표적 추적에서 표적의 소멸·출현을 다루는 표준 트릭이다.

3. 쌍대변수와 상보 여유[편집]

헝가리안 알고리즘의 모든 단계는 사실 쌍대 문제에서 벌어진다. 위 LP의 쌍대는

\max \sum_i u_i + \sum_j v_j \quad\text{s.t.}\quad u_i + v_j \le c_{ij}\ \ \forall i,j

이고, 여기서 $u_i, v_j$ 를 퍼텐셜(potential) 또는 쌍대변수라 부른다. 축소비용을

\bar{c}_{ij} = c_{ij} - u_i - v_j \ \ge 0

로 두면 쌍대 실행가능성은 “축소비용이 전부 음이 아니다”와 같은 말이다. 그리고 상보 여유 조건은

x_{ij} > 0 \ \Longrightarrow\ \bar{c}_{ij} = 0

이다. 즉 축소비용이 0인 간선만 골라 완전 매칭을 만들 수 있으면 그 매칭이 최적이다. 축소비용 0인 간선들만 모은 부분그래프를 등식 부분그래프(equality subgraph)라 부른다.

여기서 알고리즘의 골격이 그대로 나온다.

쌍대 실행가능한 $u, v$ 를 하나 잡는다.
등식 부분그래프에서 최대 매칭을 찾는다. 완전 매칭이면 끝 — 최적성이 증명된 상태다.
완전 매칭이 없으면 홀 조건이 깨진 병목 집합이 드러난다. 그 정보로 $u, v$ 를 최소량만큼 조정해 등식 부분그래프에 새 간선을 편입시키고 2로 돌아간다.

원 문제(매칭)와 쌍대 문제(퍼텐셜)를 번갈아 밀어 올린다는 점에서 전형적인 원-쌍대 알고리즘이며, 종료 시점에 최적성 증명서(쌍대해)가 공짜로 딸려 나온다는 것이 큰 장점이다. 실무에서 “이 배정이 정말 최적이냐”는 질문에 $u, v$ 를 내밀면 검증이 $O(n^2)$ 에 끝난다.

4. 표 형태 — 행·열 감산과 최소 덮개[편집]

교과서에 실리는 손계산 절차는 위 골격을 행렬 조작으로 옮긴 것이다.

행 감산 — 각 행에서 그 행의 최솟값을 뺀다. (이게 $u_i$ 다.)
열 감산 — 각 열에서 그 열의 최솟값을 뺀다. (이게 $v_j$ 다.) 이제 모든 성분이 축소비용 $\bar{c}_{ij} \ge 0$ 이고, 각 행·열에 0이 최소 하나씩 있다.
최소 덮개 — 0인 성분을 전부 덮는 데 필요한 최소 개수의 가로·세로 줄을 긋는다. 줄이 $n$ 개면 0들 사이에 완전 매칭이 존재하므로 그것을 읽어내고 종료.
쌍대 갱신 — 줄이 $n$ 개 미만이면, 덮이지 않은 성분 중 최솟값 $h$ 를 찾아 덮이지 않은 모든 성분에서 $h$ 를 빼고, 두 줄에 겹쳐 덮인 성분에는 $h$ 를 더한다. 3으로 돌아간다.

3단계의 “최소 덮개”가 정확히 이분 매칭의 최소 정점 덮개이고, “줄 개수 $=n$ 이면 완전 매칭”이 바로 쾨니그 정리다. 즉 이 절차는 쾨니그 정리를 매 반복마다 호출하고 있는 셈이라, 알고리즘 이름이 왜 헝가리 수학자들에게 헌정됐는지가 여기서 드러난다.

4단계도 쌍대 갱신을 행렬 언어로 번역한 것뿐이다. 덮이지 않은 행의 $u_i$ 를 $h$ 만큼 올리고 덮인 열의 $v_j$ 를 $h$ 만큼 내리면, 덮이지 않은 성분은 $h$ 만큼 줄고 이중으로 덮인 성분은 $h$ 만큼 늘며 한 줄만 덮인 성분은 그대로다. **음수가 생기지 않도록 하는 최대 증분이 정확히 $h$ **라서, 이 갱신은 쌍대 실행가능성을 유지하면서 쌍대 목적값을 최대한 올리는 한 걸음이다. 새 0이 최소 하나 생기므로 진전이 보장된다.

이 형태의 소박한 구현은 반복마다 덮개를 다시 계산해 $O(n^4)$ 이다. 먼크레스가 1957년에 정리한 것이 이 판본이고, 손으로 $4\times4$ 를 푸는 데는 이걸 쓰면 된다.

5. 증가경로 관점과 $O(n^3)$ [편집]

$O(n^3)$ 을 얻으려면 “덮개를 다시 긋는다”를 “증가경로를 한 번 찾는다”로 바꿔야 한다. 관점은 이렇다.

매칭되지 않은 행 하나에서 출발해, 축소비용을 간선 길이로 하는 그래프에서 매칭되지 않은 열까지의 최단 경로를 찾는다. 축소비용이 음이 아니므로 다익스트라를 그대로 쓸 수 있고, 이 최단 경로가 곧 교대 경로 — 매칭 간선과 비매칭 간선이 번갈아 나오는 경로 — 가 되도록 방향을 잡는다. 경로를 찾으면 그 위에서 매칭을 뒤집어 매칭 크기를 1 늘린다. 동시에 다익스트라가 계산한 거리 $d_j$ 로 퍼텐셜을 갱신한다.

u_i \mathrel{+}= \delta - d_i, \qquad v_j \mathrel{-}= \delta - d_j

(정확한 부호와 대상 집합은 구현마다 다르지만, 요지는 다익스트라 거리가 곧 다음 쌍대 갱신량이라는 것이다.) 이 갱신 덕분에 방금 찾은 최단 경로 위의 간선들이 등식 부분그래프에 편입되고, 축소비용의 비음성은 유지된다.

증가는 정확히 $n$ 번, 각 다익스트라가 조밀 구현으로 $O(n^2)$ 이므로 총

O(n^3)

이다. 이 형태를 보통 최단 증가경로 헝가리안이라 부르며, 토미자와(1971)와 에드먼즈-카프(1972)가 정리한 것이 원형이다. 희소 비용행렬( $m \ll n^2$ )이라면 힙 기반 다익스트라로 $O(n(m + n\log n))$ 까지 내려간다.

여기까지 오면 할당 문제가 최소 비용 흐름의 특수한 경우임이 분명해진다. 소스에서 각 행으로 용량 1, 각 열에서 싱크로 용량 1, 행-열 간선의 비용이 $c_{ij}$ 인 네트워크에 연속 최단경로법을 돌린 것과 정확히 같은 절차다. 실제로 문제 규모가 크거나 구조가 지저분하면 전용 헝가리안 구현을 짜는 대신 최소비용 흐름 솔버를 부르는 것이 낫다.

6. JV와 경매 알고리즘[편집]

이론 복잡도는 $O(n^3)$ 에서 오래 멈춰 있지만, 상수를 깎는 경쟁은 계속됐다.

JV 알고리즘(Jonker–Volgenant, 1987)은 위 최단 증가경로 골격에 강력한 초기화를 붙인 것이다. 열 감산으로 시작해 축소 이전(reduction transfer), 증가 행 감산(augmenting row reduction)이라는 값싼 그리디 단계를 먼저 돌려 대부분의 행을 미리 매칭시켜 놓고, 남은 소수의 행에 대해서만 다익스트라를 돌린다. 점근 복잡도는 그대로지만 실측 속도가 몇 배 빨라져, 오늘날 사실상의 표준 구현이 됐다. SciPy의 linear_sum_assignment도 직사각 행렬을 직접 다루도록 수정한 JV 변형이다.

경매 알고리즘(auction algorithm, 베르트세카스)은 발상 자체가 다르다. 최대화 형태로 놓고 각 작업 $j$ 에 가격 $p_j$ 를 매긴다.

짝 없는 일꾼 $i$ 가 자기 이익 $a_{ij} - p_j$ 가 최대인 작업 $j^\star$ 를 고른다.
최대 이익과 차순위 이익의 차이에 $\varepsilon$ 을 더한 만큼 가격을 올려 입찰한다.
최고 입찰자가 그 작업을 가져가고, 원래 주인은 짝 없는 상태로 돌아간다.

가격이 곧 쌍대변수이고, 입찰은 $\varepsilon$ -상보 여유를 유지하는 쌍대 상승이다. 이 알고리즘은 최적해에서 최대 $n\varepsilon$ 만큼 떨어진 해를 주며, 비용이 정수이고 $\varepsilon < 1/n$ 이면 정확히 최적이다. 소박하게 돌리면 반복 수가 비용 크기에 의존하는 유사다항이지만, $\varepsilon$ 을 크게 시작해 점점 줄이는 $\varepsilon$ -스케일링을 쓰면 다항 경계가 나온다. 진짜 매력은 다른 데 있다 — 입찰이 일꾼별로 독립이라 병렬화가 자연스럽다. 헝가리안의 다익스트라는 본질적으로 순차적인데, 경매는 GPU와 분산 환경에서 그대로 펼쳐진다.²

한계도 알아 두면 좋다. 비용에 쌍 사이의 상호작용이 들어가는 순간 — 예컨대 “ $i$ 와 $i'$ 를 서로 가까운 자리에 배정하면 이득” — 문제는 이차 할당 문제가 되고 NP-난해로 올라간다. 할당 문제가 쉬운 것은 목적함수가 선형이고 제약이 이분 구조일 때뿐이라는 점은 이분 매칭의 사정과 똑같다.

7. 어디에 쓰이나[편집]

다중 표적 추적(MOT). 프레임마다 검출된 물체와 기존 궤적을 잇는 데이터 연관 문제가 전형적인 할당 문제다. 비용은 칼만 필터 예측 위치와의 마할라노비스 거리, IoU, 외형 특징 거리 등을 섞어 만들고, 게이팅으로 말도 안 되는 쌍은 미리 무한대로 막는다. 검출 실패와 신규 출현은 더미 행·열로 흡수한다. 실시간 추적기 상당수가 프레임당 헝가리안 한 번이라는 단순한 구조로 돌아가며, 클러터가 심해 단일 최적 배정이 위험한 상황에서는 확률적 데이터 연관이나 다중 가설 추적으로 올라간다. 센서 융합의 표준 부품.
자원 배분·스케줄링. 승무원-비행편, 기계-작업, 작업-GPU, 배차-호출. 부하가 시간에 따라 바뀌면 매 주기 재배정하게 되고, 이 지점에서 부하 분산의 중앙집중식 스케줄러와 만난다.
희소 직접법의 정적 피벗팅. 희소행렬을 LU 분해하기 전에 대각 원소의 곱을 최대화하도록 행을 재배열하는 MC64류 전처리가 정확히 할당 문제다. 이 얘기는 이분 매칭에 정리돼 있다.
점 대응 문제. 두 점군 사이의 대응을 찾는 문제(ICP 변형, 특징점 매칭)에서 거리 행렬을 비용으로 놓는다.
이산 최적 수송의 특수 경우. 양쪽 주변분포가 균등하고 질량이 같으면 최적 수송 문제가 곧 할당 문제다. 대규모에서는 엔트로피 정규화를 얹은 싱크혼 반복이 GPU 친화적이라 자주 대체하는데, 그 대신 정확한 순열이 아니라 소프트 대응을 얻는다는 차이가 있다.

실무 팁 하나. $n$ 이 몇 백을 넘어가면 비용행렬을 만드는 데 드는 $O(n^2)$ 이 알고리즘보다 아프다. 추적기에서 게이팅으로 후보를 미리 쳐내는 것, 즉 희소화가 대개 헝가리안 구현을 최적화하는 것보다 훨씬 큰 이득을 준다.³

8. 관련 문서[편집]

쿤 본인이 나중에 밝힌 바로는, 야코비가 19세기에 사실상 같은 방법을 라틴어 유고로 남겼다는 사실이 20세기 말에야 발견됐다. 그래서 일각에서는 “야코비 방법”이라 불러야 한다는 주장도 있는데, 이 바닥에서 원조를 따지기 시작하면 대개 200년 전 누군가가 이미 해 놨다는 결론에 도달한다. ↩
경매 알고리즘의 이름은 은유가 아니라 실제 경제학적 해석이다. 가격이 오르는 과정이 쌍대 상승이고, 균형 가격에서의 배정이 최적해다. 발라스 균형을 알고리즘으로 구현하면 조합 최적화 문제가 풀린다는 이야기라, 경제학 수업에서 예시로 끌려 나오는 일이 잦다. ↩
“우리 추적기가 느려요” → 프로파일링해 보면 헝가리안이 아니라 외형 특징 추출 CNN이 99%를 먹고 있는 경우가 압도적이다. 1955년 알고리즘이 2020년대 병목이 되는 일은 생각보다 드물다. ↩