Hungarian Algorithm | imeimi / Algorithm DB

1개요

Hungarian은 |L| = |R| = n인 이분 그래프와 비용 함수 c: L × R → ℝ_≥0이 주어졌을 때 비용 합 ∑_(i,j)∈M c_i,j가 최소인 완전 매칭 M을 구한다.

각 L-정점 i마다 잠재 비용(potential) u_i, 각 R-정점 j마다 v_j를 대응시킨다. u_i + v_j ≤ c_i,j (∀i ∈ L, ∀j ∈ R)를 실현 가능 쌍대(feasible dual) 조건이라 한다.

축소 비용(reduced cost)을 c'_i,j = c_i,j − u_i − v_j ≥ 0으로 정의한다.

실현 가능 쌍대 (u, v)와 완전 매칭 M에 대해 ∑_(i,j)∈M c_i,j ≥ ∑_i∈L u_i + ∑_j∈R v_j이 성립한다.

∑_(i,j)∈M c_i,j = ∑_(i,j)∈M (u_i + v_j + c'_i,j) ≥ ∑_(i,j)∈M (u_i + v_j) = ∑_i∈L u_i + ∑_j∈R v_j.

마지막 등호는 M이 완전 매칭이므로 각 i ∈ L과 j ∈ R이 정확히 한 번씩 등장하기 때문이다. ■

따름 정리: 완전 매칭 M에서 ∀(i,j) ∈ M: c'_i,j = 0이면 M은 최소 비용이다.

실현 가능 쌍대 (u, v)에 대해 동등 부분 그래프(equality subgraph)를

E_h = {(i,j) : c'_i,j = 0}

로 정의한다. E_h 안에 완전 매칭이 존재하면 최소 비용이다.

∀i ∈ L: u_i = min_j∈R c_i,j, ∀j ∈ R: v_j = 0으로 초기화한다. 그러면 c'_i,j = c_i,j − u_i ≥ 0이므로 실현 가능하다.

실현 가능 쌍대를 유지하면서 E_h 안의 증가 경로를 반복 탐색해 매칭을 키운다. 미매칭 L-정점마다 다음 증가 단계를 수행한다.

미매칭 L-정점 i₀에서 시작한다. S = {i₀}, T = ∅로 놓고, 각 j ∈ R에 대해 dist_j = c'_i₀,j를 계산한 후 다음을 반복한다.

j* = argmin_j∉T dist_j를 구한다. δ = dist_j*.
i ∈ S이면 u_i ← u_i + δ, j ∈ T이면 v_j ← v_j − δ. dist_j도 j ∉ T인 것들에 대해 δ만큼 줄인다.
j*가 미매칭이면 i₀ ⋯ j* 교차 경로를 따라 매칭을 뒤집고 증가 단계를 종료한다.
j*가 매칭됨이면 T ← T ∪ {j*}, S ← S ∪ {match(j*)}로 확장한다. 새로 추가된 i* = match(j*)에 대해 ∀j ∉ T: dist_j ← min(dist_j, c'_i*,j)로 갱신한다.

매 반복에서 |T|가 증가하므로 증가 단계는 n번 이하의 반복으로 종료한다.

n번의 증가 단계 후 완전 매칭 M을 얻는다. 시간 복잡도는 O(n³).

알고리즘이 실행되는 동안 실현 가능 쌍대 조건 ∀i ∈ L, ∀j ∈ R: c'_i,j ≥ 0이 유지된다.

쌍대 갱신 횟수에 대한 귀납법을 사용한다.

기저 (갱신 0회): 초기화 직후 c'_i,j = c_i,j − u_i ≥ 0이므로 실현 가능하다.

귀납 (갱신 1회 이상): 직전 상태가 실현 가능하다고 가정하자. 한 번의 δ 갱신에서 각 쌍 (i, j)의 축소 비용 변화 Δc'_i,j는 i, j의 S, T 소속에 따라 나뉜다.

(i ∈ S, j ∈ T): u_i가 +δ, v_j가 −δ이므로 Δc'_i,j = 0.
(i ∈ S, j ∉ T): u_i가 +δ. Δc'_i,j = −δ. δ의 정의에 의해 c'_i,j ≥ δ였으므로 c'_i,j ≥ 0이 유지된다.
(i ∉ S, j ∈ T): v_j가 −δ. Δc'_i,j = δ ≥ 0.
(i ∉ S, j ∉ T): Δc'_i,j = 0.

네 경우 모두 c'_i,j ≥ 0이 유지된다. ■

종료 시 얻는 완전 매칭 M은 E_h 안에 있으므로 ∀(i,j) ∈ M: c'_i,j = 0이고, 보조 정리 1의 따름 정리에 의해 M은 최소 비용이다. ■

Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2), 83–97.
Jonker, R., & Volgenant, A. (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38(4), 325–340.