작업 할당 최적화를 위한 헝가리안 알고리즘 (Hungarian Matching Algorithm)

헝가리안 (Hungarian) 알고리즘은 1955년 Harold Kuhn 에 의해 개발 및 발표되었으며, 이 알고리즘이 두 명의 헝가리 수학자 Dénes Kőnig 와 Jenő Egerváry 의 초기 연구에 크게 기반을 두고 있기 때문에 "헝가리안 방법"이라는 이름을 붙였습니다.

헝가리안 알고리즘은 어디에 사용될까?

헝가리안 매칭 알고리즘은 할당 문제(Assignment Problem)를 해결합니다:

“n개의 작업을 n명의 작업자에게 어떻게 할당하면 총 비용이 최소화되거나 총 이익이 최대화될까?”

이 문제는 다음과 같이 생각할 수 있습니다:

• 작업을 직원에게 최적 할당
• 예측 박스와 실제 GT 박스 매칭
• 학생과 학교의 최적 매칭
• DETR (End-to-End Object Detection with Transformers)에서 predicted bbox를 GT box와 매칭 

---

예제 문제

3명의 작업자와 3개의 작업이 있습니다. 아래의 비용 매트릭스는 특정 작업자를 특정 작업에 할당할 때의 비용을 나타냅니다.

비용 행렬:
          작업1 작업2 작업3
작업자1     9     2     7
작업자2     6     4     3
작업자3     5     8     1

각 작업자에게 하나의 작업을 할당하되 총 비용이 최소화되도록 하고 싶습니다.

알고리즘 개요

헝가리안 알고리즘은 다음 단계로 작동합니다:

[1] 각 행의 최소값을 뺍니다     → 모든 행에 0이 있도록 만듭니다
[2] 각 열의 최소값을 뺍니다     → 모든 열에 0이 있도록 합니다
[3] 0을 스타로 표시합니다       → 행/열에 겹치지 않는 독립적인 0을 선택합니다
[4] 스타가 있는 열을 커버합니다 → 가능한 모든 작업을 커버합니다
[5] 최적이 아닐 경우:
    ↓ 새로운 0을 찾고 프라임으로 표시
    ↓ 커버 업데이트 및 교대 경로 생성
    ↓ 행렬 조정 (가장 작은 커버되지 않은 값을 더하거나 뺌)
모든 행이 할당될 때까지 반복

Pseudo 코드 분석

다음은 헝가리안 알고리즘의 pseudo코드입니다:

입력: cost_matrix[n][n]

1. 각 행에 대해, 해당 행의 최소값을 모든 요소에서 뺍니다
2. 각 열에 대해, 해당 열의 최소값을 모든 요소에서 뺍니다

3. 0을 스타로 표시:
   - 각 0에 대해, 그 행과 열이 커버되지 않은 경우 스타로 표시
   - 해당 행과 열은 일시적으로 커버

4. 스타가 있는 열을 커버
   - 모든 열이 커버되면 종료
   - 그렇지 않으면 5단계로 이동

5. 모든 열이 커버될 때까지 반복:
   a. 커버되지 않은 0을 찾고 프라임으로 표시
   b. 같은 행에 스타가 없으면:
       - 스타와 프라임으로 교대 경로 생성
       - 스타 제거, 프라임을 스타로 전환
       - 커버 초기화 후 4단계로 이동
   c. 그렇지 않으면:
       - 해당 행을 커버하고, 스타가 있는 열을 언커버
       - 다시 검색 반복

6. 커버되지 않은 0이 없으면:
   - 가장 작은 커버되지 않은 값을 찾고
   - 커버되지 않은 요소에서 뺍니다
   - 두 번 커버된 요소에는 더합니다
   - 5단계로 돌아갑니다

---

예제

아래 행렬에 헝가리안 알고리즘을 적용해봅시다:

[9, 2, 7]
[6, 4, 3]
[5, 8, 1]

행의 최소값을 뺍니다:

행 최소값 = [2, 3, 1]
결과:
[7, 0, 5]
[3, 1, 0]
[4, 7, 0]

열의 최소값을 뺍니다:

열 최소값 = [3, 0, 0]
결과:
[4, 0, 5]
[0, 1, 0]
[1, 7, 0]

겹치지 않는 0을 스타로 표시:

[4, *0, 5]
[*0, 1, 0] ← 겹침
[1, 7, *0]

최종 스타:
(0,1), (1,0), (2,2)

→ 커버된 열 = 3개 → 모두 매칭 완료!

보다 상세한 자료는 아래 링크된 페이지들에서 보실 수 있습니다.

---

참고 자료

1. 헝가리안 알고리즘 (위키백과): https://en.wikipedia.org/wiki/Hungarian_algorithm
2. 헝가리안 알고리즘 시각화 자료: https://brc2.com/the-algorithm-workshop/