할당 문제를 해결하기 위한 헝가리안 알고리즘¶

할당 문제의 정의¶

할당 문제에는 몇 가지 표준적인 정식화가 있습니다(이들은 모두 본질적으로 동등합니다). 그중 몇 가지는 다음과 같습니다:

$n$개의 작업과 $n$명의 작업자가 있습니다. 각 작업자는 특정 작업에 대해 자신이 기대하는 금액을 제시합니다. 각 작업자는 오직 하나의 작업에만 할당될 수 있습니다. 목표는 총비용이 최소가 되도록 작업자에게 작업을 할당하는 것입니다.
$n \times n$ 행렬 $A$가 주어졌을 때, 각 열에서 정확히 하나의 수가 선택되도록 각 행에서 수를 하나씩 선택하되, 선택된 수들의 합이 최소가 되도록 하는 것이 과제입니다.
$n \times n$ 행렬 $A$가 주어졌을 때, 값 $\sum A[i]\left[p[i]\right]$가 최소가 되도록 하는 길이 $n$의 순열 $p$를 찾는 것이 과제입니다.
각 부분마다 $n$개의 정점이 있고 각 간선에 가중치가 부여된 완전 이분 그래프를 생각해 봅시다. 목표는 총가중치가 최소인 완전 매칭을 찾는 것입니다.

위의 모든 시나리오는 "정사각형" 문제, 즉 두 차원이 항상 $n$으로 같은 문제라는 점에 유의해야 합니다. 실제로는 $n$이 $m$과 같지 않고 $\min(n,m)$개의 원소를 선택해야 하는 비슷한 "직사각형" 정식화를 자주 접하게 됩니다. 그러나 "직사각형" 문제는 값이 각각 0 또는 무한대인 행이나 열을 추가하여 항상 "정사각형" 문제로 변환할 수 있음을 알 수 있습니다.

또한 최소 해를 찾는 것과 마찬가지로 최대 해를 찾는 문제도 제기할 수 있습니다. 그러나 이 두 문제는 서로 동등합니다: 모든 가중치에 $-1$을 곱하기만 하면 됩니다.

헝가리안 알고리즘¶

역사적 배경¶

이 알고리즘은 1955년 Harold Kuhn이 개발하여 발표했습니다. Kuhn 자신은 이 알고리즘이 헝가리 수학자 Dénes Kőnig와 Jenő Egerváry의 초기 연구에 기반을 두었기 때문에 "헝가리안"이라는 이름을 붙였습니다.
1957년 James Munkres는 이 알고리즘이 비용과 무관하게 (엄밀한) 다항 시간에 동작함을 보였습니다.
따라서 문헌에서 이 알고리즘은 "헝가리안" 알고리즘뿐만 아니라 "Kuhn-Munkres 알고리즘" 또는 "Munkres 알고리즘"으로도 알려져 있습니다.
그러나 2006년에 와서야 같은 알고리즘이 Kuhn보다 한 세기 앞서 독일 수학자 Carl Gustav Jacobi에 의해 고안되었다는 사실이 밝혀졌습니다. 그의 사후인 1890년에 출판된 저작 임의의 상미분 방정식계의 차수에 관한 연구에는 여러 발견과 함께 할당 문제를 해결하는 다항 시간 알고리즘이 담겨 있었습니다. 안타깝게도 이 저작은 라틴어로 출판되었기 때문에 수학자들 사이에서 주목받지 못했습니다.

또한 Kuhn의 원래 알고리즘은 점근적 복잡도가 $\mathcal{O}(n^4)$였으며, 이후에야 Jack Edmonds와 Richard Karp가 (그리고 독립적으로 Tomizawa가) 이를 점근적 복잡도 $\mathcal{O}(n^3)$으로 개선하는 방법을 보였다는 점도 주목할 만합니다.

$\mathcal{O}(n^4)$ 알고리즘¶

모호함을 피하기 위해 먼저 밝혀 두자면, 여기서는 주로 행렬 정식화의 할당 문제를 다룹니다(즉, 행렬 $A$가 주어졌을 때 서로 다른 행과 열에 있는 $n$개의 칸을 선택해야 합니다). 배열의 인덱스는 $1$부터 시작합니다. 예를 들어 행렬 $A$의 인덱스는 $A[1 \dots n][1 \dots n]$입니다.

또한 행렬 A의 모든 수가 음이 아니라고 가정하겠습니다(그렇지 않은 경우에도 모든 수에 어떤 상수를 더하여 행렬을 항상 음이 아니게 만들 수 있습니다).

다음 조건을 만족하는 임의의 두 수 배열 $u[1 \ldots n]$과 $v[1 \ldots n]$을 포텐셜이라고 부릅시다:

$$u[i]+v[j]\leq A[i][j],\quad i=1\dots n,\ j=1\dots n$$

(보시다시피 $u[i]$는 행렬의 $i$번째 행에, $v[j]$는 $j$번째 열에 대응합니다).

포텐셜 원소들의 합을 포텐셜의 값 $f$라고 부릅시다:

$$f=\sum_{i=1}^{n} u[i] + \sum_{j=1}^{n} v[j].$$

한편으로, 구하고자 하는 해 $sol$의 비용이 어떤 포텐셜의 값보다도 작지 않다는 것은 쉽게 알 수 있습니다.

보조정리. $sol\geq f.$

증명

문제에서 구하려는 해는 행렬 $A$의 칸 $n$개로 이루어지므로, 각 칸에 대해 $u[i]+v[j]\leq A[i][j]$가 성립합니다. $sol$의 모든 원소는 서로 다른 행과 열에 있으므로, 선택된 모든 $A[i][j]$에 대해 이 부등식들을 더하면 부등식의 왼쪽에는 $f$가, 오른쪽에는 $sol$이 남습니다.

한편, 이 부등식을 등식으로 만드는 해와 포텐셜이 항상 존재한다는 사실이 밝혀져 있습니다. 아래에서 설명할 헝가리안 알고리즘이 이 사실의 구성적 증명이 됩니다. 지금은 어떤 해의 비용이 어떤 포텐셜의 값과 같다면 그 해가 최적이라는 사실에만 주목합시다.

어떤 포텐셜을 하나 고정합시다. $u[i]+v[j]=A[i][j].$이면 간선 $(i,j)$를 강직(rigid) 간선이라고 부릅시다.

이분 그래프를 이용한 할당 문제의 다른 정식화를 떠올려 보십시오. 강성 간선만으로 이루어진 이분 그래프를 $H$로 표기합시다. 헝가리안 알고리즘은 현재 포텐셜에 대해 그래프 $H$의 간선 수가 최대인 매칭 $M$을 유지합니다. $M$이 간선 $n$개를 포함하게 되면 문제의 해는 바로 $M$이 됩니다(결국 비용이 포텐셜의 값과 일치하는 해가 되기 때문입니다).

이제 바로 알고리즘의 설명으로 넘어갑시다.

1단계. 처음에는 포텐셜을 0으로(모든 $i$에 대해 $u[i]=v[i]=0$) 두고, 매칭 $M$은 비어 있다고 둡니다.

2단계. 이후 알고리즘의 각 단계에서는 포텐셜을 바꾸지 않은 채 현재 매칭 $M$의 크기를 1만큼 늘리려고 시도합니다(매칭은 강성 간선으로 이루어진 그래프 $H$에서 찾는다는 점을 기억하십시오). 이를 위해 일반적인 이분 그래프에서 최대 매칭을 찾는 Kuhn 알고리즘을 사용합니다. 여기서 이 알고리즘을 다시 떠올려 봅시다. 매칭 $M$의 모든 간선은 오른쪽 부분에서 왼쪽 부분으로 향하도록 방향을 정하고, 그래프 $H$의 나머지 간선은 모두 반대 방향으로 정합니다.

(매칭 탐색의 용어로) 현재 매칭의 간선이 인접한 정점을 포화(saturated) 정점이라고 부른다는 것을 떠올리십시오. 현재 매칭의 어떤 간선에도 인접하지 않은 정점은 불포화(unsaturated) 정점이라고 부릅니다. 길이가 홀수이고, 첫 번째 간선은 매칭에 속하지 않으며, 이후의 간선들은 매칭에 속하는지 여부가 번갈아 나타나는(속함/속하지 않음) 경로를 증가 경로라고 부릅니다. 왼쪽 부분의 모든 불포화 정점에서 깊이 우선 또는 너비 우선 순회를 시작합니다. 탐색 결과 오른쪽 부분의 불포화 정점에 도달할 수 있었다면, 왼쪽 부분에서 오른쪽 부분으로 가는 증가 경로를 찾은 것입니다. 경로의 홀수 번째 간선을 매칭에 포함하고 짝수 번째 간선을 매칭에서 제거하면(즉, 첫 번째 간선을 매칭에 포함하고, 두 번째를 제외하고, 세 번째를 포함하는 식으로 진행하면) 매칭의 크기가 1만큼 늘어납니다.

증가 경로가 없었다면 현재 매칭 $M$은 그래프 $H$에서 최대입니다.

3단계. 현재 단계에서 현재 매칭의 크기를 늘릴 수 없다면, 다음 단계들에서 매칭을 늘릴 기회가 더 많아지도록 포텐셜을 다시 계산합니다.

Kuhn 알고리즘의 마지막 순회에서 방문한 왼쪽 부분의 정점 집합을 $Z_1$로, 방문한 오른쪽 부분의 정점 집합을 $Z_2$로 나타냅시다.

값 $\Delta$를 계산해 봅시다:

$$\Delta = \min_{i\in Z_1,\ j\notin Z_2} A[i][j]-u[i]-v[j].$$

보조정리. $\Delta > 0.$

증명

$\Delta=0$이라고 가정합시다. 그러면 $i\in Z_1$이고 $j\notin Z_2$인 강성 간선 $(i,j)$가 존재합니다. 따라서 간선 $(i,j)$는 오른쪽 부분에서 왼쪽 부분으로 향해야 합니다. 즉, $(i,j)$는 매칭 $M$에 포함되어야 합니다. 그러나 이는 불가능합니다. 포화된 정점 $i$에는 j에서 i로 가는 간선을 따라가는 방법 외에는 도달할 수 없기 때문입니다. 따라서 $\Delta > 0$입니다.

이제 다음과 같이 포텐셜을 다시 계산해 봅시다.

모든 정점 $i\in Z_1$에 대해 $u[i] \gets u[i]+\Delta$를 수행하고,
모든 정점 $j\in Z_2$에 대해 $v[j] \gets v[j]-\Delta$를 수행합니다.

보조정리. 이렇게 얻은 포텐셜은 여전히 올바른 포텐셜입니다.

증명

다시 계산한 뒤에도 모든 $i,j$에 대해 $u[i]+v[j]\leq A[i][j]$임을 보이겠습니다. $i\in Z_1$이고 $j\in Z_2$인 $A$의 모든 원소에 대해서는 합 $u[i]+v[j]$가 변하지 않으므로 부등식이 계속 성립합니다. $i\notin Z_1$이고 $j\in Z_2$인 모든 원소에 대해서는 합 $u[i]+v[j]$가 $\Delta$만큼 감소하므로 부등식이 여전히 성립합니다. $i\in Z_1$이고 $j\notin Z_2$인 나머지 원소에 대해서는 합이 증가하지만, 값 $\Delta$는 정의상 부등식을 깨뜨리지 않는 최대 증가량이므로 부등식은 여전히 유지됩니다.

보조정리. 강성 간선으로 이루어진 기존 매칭 $M$은 유효합니다. 즉, 매칭의 모든 간선은 강성 간선으로 남습니다.

증명

어떤 강성 간선 $(i,j)$가 포텐셜 변화로 인해 더 이상 강성 간선이 아니게 되려면, 등식 $u[i] + v[j] = A[i][j]$가 부등식 $u[i] + v[j] < A[i][j]$로 바뀌어야 합니다. 그러나 이는 $i \notin Z_1$이고 $j \in Z_2$일 때만 일어날 수 있습니다. 하지만 $i \notin Z_1$이라면 간선 $(i,j)$는 매칭 간선일 수 없습니다.

보조정리. 포텐셜을 다시 계산할 때마다 탐색으로 도달할 수 있는 정점의 수, 즉 $|Z_1|+|Z_2|$는 엄격하게 증가합니다.

증명

먼저, 다시 계산하기 전에 도달할 수 있었던 정점에는 여전히 도달할 수 있다는 점에 주목하십시오. 실제로, 어떤 정점에 도달할 수 있다면 왼쪽 부분의 포화되지 않은 정점에서 시작하여 도달 가능한 정점들을 거쳐 그 정점에 이르는 경로가 존재합니다. $(i,j),\ i\in Z_1,\ j\in Z_2$ 꼴의 간선에 대해서는 합 $u[i]+v[j]$가 변하지 않으므로, 포텐셜을 바꾼 뒤에도 이 경로 전체가 그대로 유지됩니다. 둘째로, 다시 계산한 뒤에는 적어도 하나의 새로운 정점에 도달할 수 있음을 보이겠습니다. 이는 $\Delta$의 정의에서 나옵니다. $\Delta$에 해당하는 간선 $(i,j)$가 강성 간선이 되므로, 정점 $i$에서 정점 $j$에 도달할 수 있게 됩니다.

마지막 보조정리에 따라, 증가 경로를 찾아 $M$의 매칭 크기가 증가하기 전까지 포텐셜 재계산은 최대 $n$번만 일어날 수 있습니다. 따라서 언젠가는 완전 매칭 $M^*$에 대응하는 포텐셜을 찾게 되며, $M^*$가 문제의 답이 됩니다. 알고리즘의 복잡도를 말하자면 $\mathcal{O}(n^4)$입니다. 매칭은 전체적으로 최대 $n$번 증가하고, 각 증가 전에는 최대 $n$번의 포텐셜 재계산이 일어나며, 각 재계산은 $\mathcal{O}(n^2)$ 시간에 수행되기 때문입니다.

$\mathcal{O}(n^4)$ 알고리즘의 구현은 아래에서 설명할 $\mathcal{O}(n^3)$ 알고리즘의 구현보다 짧지 않으므로 여기서는 제시하지 않겠습니다.

$\mathcal{O}(n^3)$ 알고리즘¶

이제 같은 알고리즘을 $\mathcal{O}(n^3)$에(직사각형 $n \times m$ 문제의 경우 $\mathcal{O}(n^2m)$에) 구현하는 방법을 알아봅시다.

핵심 아이디어는 행렬의 행을 한꺼번에 모두 고려하지 않고 하나씩 차례로 고려하는 것입니다. 따라서 앞에서 설명한 알고리즘은 다음과 같은 형태가 됩니다.

행렬 $A$의 다음 행을 고려합니다.
이 행에서 시작하는 증가 경로가 없는 동안 포텐셜을 다시 계산합니다.
증가 경로를 찾으면 곧바로 그 경로를 따라 매칭을 전파하고(이로써 마지막 간선이 매칭에 포함됩니다), (다음 행을 고려하기 위해) 1단계부터 다시 시작합니다.

요구되는 복잡도를 달성하려면 행렬의 각 행마다 수행되는 2~3단계를 $\mathcal{O}(n^2)$ 시간(직사각형 문제에서는 $\mathcal{O}(nm)$ 시간)에 구현해야 합니다.

이를 위해 앞에서 증명한 두 가지 사실을 떠올려 봅시다.

포텐셜이 바뀌어도 Kuhn 탐색으로 도달할 수 있었던 정점은 계속 도달 가능합니다.
증가 경로를 찾기 전까지 포텐셜 재계산은 모두 합해 $\mathcal{O}(n)$번만 일어날 수 있습니다.

이로부터 요구되는 복잡도를 달성할 수 있게 해 주는 다음과 같은 핵심 아이디어가 도출됩니다.

증가 경로가 존재하는지 확인하기 위해 포텐셜을 재계산할 때마다 Kuhn 탐색을 처음부터 다시 시작할 필요는 없습니다. 대신 Kuhn 탐색을 반복적 형태로 수행할 수 있습니다. 포텐셜을 재계산할 때마다 새로 추가된 강성 간선(rigid edge)을 살펴보고, 그 왼쪽 끝점이 도달 가능했다면 오른쪽 끝점도 도달 가능한 것으로 표시한 뒤 그곳에서부터 탐색을 이어 가십시오.
이 아이디어를 더 발전시키면 알고리즘을 다음과 같이 나타낼 수 있습니다. 루프의 각 단계에서 포텐셜을 다시 계산합니다. 그다음 도달 가능해진 열을 하나 찾습니다(포텐셜을 재계산할 때마다 새로운 도달 가능 정점이 생기므로 이러한 열은 항상 존재합니다). 그 열이 포화되지 않았다면 증가 사슬을 찾은 것입니다. 반대로 그 열이 포화되어 있다면 그 열과 매칭된 행도 도달 가능해집니다.
포텐셜을 ($\mathcal{O}(n^2)$ 단순한 방식보다) 빠르게 재계산하려면 각 열에 대해 보조 최솟값을 유지해야 합니다.

$minv[j]=\min_{i\in Z_1} A[i][j]-u[i]-v[j].$

구하려는 값 $\Delta$가 이 값들을 사용해 다음과 같이 표현된다는 것은 쉽게 알 수 있습니다.

$\Delta=\min_{j\notin Z_2} minv[j].$

따라서 이제 $\Delta$는 $\mathcal{O}(n)$에 구할 수 있습니다.

새로 방문한 행이 생기면 배열 $minv$를 갱신해야 합니다. 이 작업은 추가된 행 하나당 $\mathcal{O}(n)$에 수행할 수 있습니다(모든 행에 대해 합하면 $\mathcal{O}(n^2)$입니다). 포텐셜을 재계산할 때에도 배열 $minv$를 갱신해야 하며, 이 역시 $\mathcal{O}(n)$ 시간에 수행됩니다($minv$는 아직 도달하지 않은 열에 대해서만 바뀌며, 구체적으로는 $\Delta$만큼 감소합니다).

따라서 알고리즘은 다음과 같은 형태가 됩니다. 바깥 루프에서 행렬의 행을 하나씩 차례로 고려합니다. 각 행은 $\mathcal{O}(n^2)$ 시간에 처리됩니다. 포텐셜 재계산은 $\mathcal{O}(n)$번만 일어날 수 있고(각각 $\mathcal{O}(n)$ 시간), 배열 $minv$는 $\mathcal{O}(n^2)$ 시간에 유지되며, Kuhn 알고리즘은 $\mathcal{O}(n^2)$ 시간에 동작하기 때문입니다(Kuhn 알고리즘은 $\mathcal{O}(n)$번의 반복으로 이루어지며, 각 반복에서 새로운 열 하나를 방문합니다).

최종 복잡도는 $\mathcal{O}(n^3)$이며, 문제가 직사각형이라면 $\mathcal{O}(n^2m)$입니다.

헝가리안 알고리즘의 구현¶

아래 구현은 몇 년 전 Andrey Lopatin이 개발한 것입니다. 이 구현은 놀라울 만큼 간결하다는 특징이 있습니다. 전체 알고리즘이 30줄의 코드로 이루어져 있습니다.

이 구현은 $n\leq m$인 직사각형 행렬 $A[1\dots n][1\dots m]$에 대한 해를 구합니다. 편의와 코드의 간결함을 위해 행렬은 1부터 인덱싱합니다. 이 구현은 더미 0번 행과 0번 열을 도입하므로, 추가 검사 없이 많은 사이클을 일반적인 형태로 작성할 수 있습니다.

배열 $u[0 \ldots n]$과 $v[0 \ldots m]$은 포텐셜을 저장합니다. 처음에는 이 배열들을 0으로 설정하며, 이는 행이 0개인 행렬과 모순되지 않습니다(이 구현에서는 행렬 $A$에 음수가 있는지 여부가 중요하지 않다는 점에 유의하십시오).

배열 $p[0 \ldots m]$은 매칭을 담습니다. 각 열 $j = 1 \ldots m$에 대해 선택된 행의 번호 $p[j]$를 저장합니다(아직 아무것도 선택되지 않았다면 $0$을 저장합니다). 구현의 편의를 위해 $p[0]$은 현재 행의 번호와 같다고 가정합니다.

배열 $minv[1 \ldots m]$은 앞서 설명한 대로 포텐셜을 빠르게 다시 계산하는 데 필요한 보조 최솟값을 각 열 $j$마다 담습니다.

배열 $way[1 \ldots m]$은 나중에 증가 경로를 복원할 수 있도록 이 최솟값들이 어디에서 달성되는지에 대한 정보를 담습니다. 행 번호는 매칭에서(즉, 배열 $p$에서) 얻을 수 있으므로, 경로를 복원하려면 열 값만 저장해도 충분하다는 점에 유의하십시오. 따라서 각 열 $j$에 대해 $way[j]$는 경로에서 이전 열의 번호를 담습니다(이전 열이 없으면 $0$을 담습니다).

알고리즘 자체는 행렬의 행을 차례로 도는 바깥쪽 루프이며, 그 안에서 행렬의 $i$번째 행을 처리합니다. 첫 번째 do-while 루프는 비어 있는 열 $j0$을 찾을 때까지 실행됩니다. 루프의 각 반복에서는 번호가 $j0$인 새 열(직전 반복에서 계산된 값이며, 처음에는 0입니다. 즉, 가상의 열에서 시작합니다)과 매칭에서 그 열에 인접한 새 행 $i0$(즉, $p[j0]$이며, 처음 $j0=0$일 때는 $i$번째 행을 사용합니다)을 방문한 것으로 표시합니다. 새로 방문한 행 $i0$이 생겼으므로 그에 맞게 배열 $minv$와 $\Delta$를 다시 계산해야 합니다. $\Delta$가 갱신되면 열 $j1$이 현재 도달한 최솟값이 됩니다(이렇게 구현하면 $\Delta$가 0이 될 수도 있다는 점에 유의하십시오. 이는 현재 단계에서 포텐셜을 바꿀 수 없다는 뜻입니다. 이미 새로 도달할 수 있는 열이 있기 때문입니다). 그다음 포텐셜과 $minv$ 배열을 다시 계산합니다. "do-while" 루프가 끝나면 열 $j0$에서 끝나는 증가 경로를 찾은 것이며, 이 경로는 조상 배열 $way$를 사용해 "풀어낼" 수 있습니다.

상수 INF는 "무한대", 즉 입력 행렬 $A$에 들어 있을 수 있는 모든 수보다 분명히 큰 어떤 수입니다.

vector<int> u (n+1), v (m+1), p (m+1), way (m+1);
for (int i=1; i<=n; ++i) {
    p[0] = i;
    int j0 = 0;
    vector<int> minv (m+1, INF);
    vector<bool> used (m+1, false);
    do {
        used[j0] = true;
        int i0 = p[j0],  delta = INF,  j1;
        for (int j=1; j<=m; ++j)
            if (!used[j]) {
                int cur = A[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);
}

답을 좀 더 익숙한 형태로 복원하려면, 즉 각 행 $i = 1 \ldots n$에 대해 그 행에서 선택된 열의 번호 $ans[i]$를 구하려면 다음과 같이 하면 됩니다:

vector<int> ans (n+1);
for (int j=1; j<=m; ++j)
    ans[p[j]] = j;

매칭의 비용은 간단히 0번 열의 포텐셜(부호를 반대로 한 값)로 구할 수 있습니다. 실제로 코드에서 볼 수 있듯이 $-v[0]$은 모든 $\Delta$ 값의 합, 즉 포텐셜의 총 변화량을 담습니다. $u[i]$와 $v[j]$의 여러 값이 한꺼번에 바뀔 수 있지만, 포텐셜의 총 변화량은 정확히 $\Delta$와 같습니다. 증가 경로가 생기기 전까지는 도달할 수 있는 행의 수가 도달할 수 있는 열의 수보다 정확히 하나 많기 때문입니다(현재 행 $i$만 방문한 열이라는 "짝"이 없습니다):

int cost = -v[0];

연속 최단 경로 알고리즘과의 관계¶

헝가리안 알고리즘은 할당 문제에 맞게 변형한 연속 최단 경로 알고리즘으로 볼 수 있습니다. 자세한 내용까지 다루지는 않고, 둘 사이의 관계를 직관적으로 살펴봅시다.

연속 최단 경로 알고리즘은 가중치 재조정 기법으로 Johnson 알고리즘을 변형한 버전을 사용합니다. 이 방법은 네 단계로 나뉩니다:

소스 $s$에서 시작하는 Bellman-Ford 알고리즘을 사용하여 각 노드에 대해 $s$에서 $v$로 가는 경로의 최소 가중치 $h(v)$를 구하십시오.

주 알고리즘의 매 단계마다 다음을 수행합니다:

원래 그래프의 간선 가중치를 다음과 같이 재조정하십시오: $w(u,v) \gets w(u,v)+h(u)-h(v)$.
Dijkstra 알고리즘을 사용하여 원래 네트워크의 최단 경로 부분 그래프를 구하십시오.
다음 반복을 위해 포텐셜을 갱신하십시오.

이 설명을 보면 $h(v)$와 포텐셜 사이에 강한 유사성이 있음을 알 수 있습니다. 실제로 두 값은 상수 차이를 제외하면 같다는 것을 확인할 수 있습니다. 또한 가중치를 재조정한 뒤에는 가중치가 0인 모든 간선의 집합이 최단 경로 부분 그래프를 이룬다는 것을 보일 수 있으며, 주 알고리즘은 이 부분 그래프에서 흐름을 증가시키려고 합니다. 헝가리안 알고리즘에서도 같은 일이 일어납니다. 강성 간선(값 $A[i][j]-u[i]-v[j]$가 0인 간선)으로 이루어진 부분 그래프를 만들고, 매칭의 크기를 늘리려고 합니다.

4단계에서는 모든 $h(v)$가 갱신됩니다. 흐름 네트워크를 수정할 때마다 소스로부터의 거리가 올바르다는 것을 보장해야 합니다(그렇지 않으면 다음 반복에서 Dijkstra 알고리즘이 실패할 수 있습니다). 이는 포텐셜에 대해 수행하는 갱신과 비슷해 보이지만, 이 경우에는 값들이 똑같이 증가하지 않습니다.

포텐셜을 더 깊이 이해하려면 이 글을 참고하십시오.

문제 예시¶

다음은 할당 문제와 관련된 몇 가지 예시로, 아주 자명한 문제부터 덜 자명한 문제까지 있습니다.

이분 그래프가 주어졌을 때, 그 안에서 최소 가중치를 갖는 최대 매칭을 찾아야 합니다(즉, 먼저 매칭의 크기를 최대화하고, 그다음으로 그 비용을 최소화합니다).
이를 해결하려면 없는 간선 자리에 "무한대" 값을 넣어 할당 문제를 구성하기만 하면 됩니다. 그런 다음 헝가리안 알고리즘으로 문제를 풀고, 답에서 가중치가 무한대인 간선을 제거합니다(문제에 완전 매칭 형태의 해가 없으면 이러한 간선이 답에 포함될 수 있습니다).
이분 그래프가 주어졌을 때, 그 안에서 최대 가중치를 갖는 최대 매칭을 찾아야 합니다.
해법은 이번에도 자명합니다. 모든 가중치에 -1을 곱하면 됩니다.
이미지에서 움직이는 물체를 탐지하는 문제: 두 장의 이미지를 촬영하여 두 개의 좌표 집합을 얻었습니다. 첫 번째 이미지와 두 번째 이미지의 물체를 서로 대응시켜야 합니다. 즉, 두 번째 이미지의 각 점이 첫 번째 이미지의 어느 점에 대응하는지 결정해야 합니다. 이 경우 대응시킨 점들 사이의 거리의 합을 최소화해야 합니다(즉, 물체들이 전체적으로 최단 경로로 이동한 해를 찾는 것입니다).
이를 해결하려면 간선의 가중치를 점들 사이의 유클리드 거리로 하는 할당 문제를 구성하여 풀기만 하면 됩니다.
탐지기로 움직이는 물체를 탐지하는 문제: 공간에서 물체의 위치는 알 수 없고 방향만 알 수 있는 탐지기가 두 개 있습니다. 두 탐지기(서로 다른 지점에 위치함)는 각각 이러한 방향 $n$개의 형태로 정보를 받았습니다. 물체의 위치를 결정해야 합니다. 즉, 물체에서 방향 반직선까지의 거리 합이 최소가 되도록 물체의 예상 위치와 그에 대응하는 방향 쌍을 결정해야 합니다.
해법: 이번에도 할당 문제를 구성하여 풀기만 하면 됩니다. 이때 왼쪽 부분의 정점은 첫 번째 탐지기의 방향 $n$개이고, 오른쪽 부분의 정점은 두 번째 탐지기의 방향 $n$개이며, 간선의 가중치는 대응하는 반직선 사이의 거리입니다.
방향 비순환 그래프를 경로로 덮기: 방향 비순환 그래프가 주어졌을 때, 그래프의 각 정점이 정확히 하나의 경로에 속하도록 하는 최소 개수의 경로(개수가 같다면 총 가중치가 최소인 경로)를 찾아야 합니다.
해법은 주어진 그래프로부터 대응하는 이분 그래프를 만들고, 그 안에서 최소 가중치를 갖는 최대 매칭을 찾는 것입니다. 자세한 내용은 별도의 글을 참고하십시오.
트리 색칠하기. 리프를 제외한 각 정점이 정확히 $k-1$개의 자식을 갖는 트리가 주어집니다. 인접한 두 정점이 같은 색을 갖지 않도록 각 정점에 사용 가능한 $k$개의 색 중 하나를 골라야 합니다. 또한 각 정점과 각 색에 대해 그 정점을 그 색으로 칠하는 비용이 알려져 있으며, 총비용을 최소화해야 합니다.
이 문제를 풀기 위해 동적 계획법을 사용합니다. 구체적으로, $d[v][c]$ 값을 계산하는 방법을 알아봅시다. 여기서 $v$는 정점 번호, $c$는 색 번호이며, $d[v][c]$ 값 자체는 정점 $v$를 색 $c$로 칠하면서 $v$를 루트로 하는 서브트리의 모든 정점을 칠하는 데 필요한 최소 비용입니다. 이러한 $d[v][c]$ 값을 계산하려면 남은 $k-1$개의 색을 정점 $v$의 자식들에게 분배해야 하며, 이를 위해 할당 문제(왼쪽 부분의 정점은 색, 오른쪽 부분의 정점은 자식, 간선의 가중치는 대응하는 $d$ 값인 문제)를 구성하여 풀어야 합니다.
따라서 각 $d[v][c]$ 값은 할당 문제의 해를 이용해 계산되며, 최종적으로 점근 복잡도 $\mathcal{O}(nk^4)$를 얻습니다.
할당 문제에서 가중치가 간선이 아니라 정점에 있고, 그것도 오직 같은 부분의 정점에만 있다면 헝가리안 알고리즘을 사용할 필요가 없습니다. 정점을 가중치 순으로 정렬한 뒤 일반적인 Kuhn 알고리즘을 실행하면 됩니다(자세한 내용은 별도의 글을 참고하십시오).
다음과 같은 특수한 경우를 생각해 봅시다. 왼쪽 부분의 각 정점에는 어떤 수 $\alpha[i]$가, 오른쪽 부분의 각 정점에는 $\beta[j]$가 할당되어 있다고 합시다. 임의의 간선 $(i,j)$의 가중치가 $\alpha[i]\cdot \beta[j]$와 같다고 합시다(수 $\alpha[i]$와 $\beta[j]$는 알려져 있습니다). 이 할당 문제를 푸십시오.
헝가리안 알고리즘 없이 이를 풀기 위해, 먼저 양쪽 부분에 정점이 두 개씩 있는 경우를 생각해 봅시다. 이 경우 쉽게 알 수 있듯이, 정점들을 역순으로 연결하는 것이 더 좋습니다. 즉, $\alpha[i]$가 더 작은 정점을 $\beta[j]$가 더 큰 정점과 연결합니다. 이 규칙은 임의의 개수의 정점으로 쉽게 일반화할 수 있습니다. 첫 번째 부분의 정점들은 $\alpha[i]$ 값의 오름차순으로, 두 번째 부분의 정점들은 $\beta[j]$ 값의 내림차순으로 정렬한 뒤, 그 순서대로 정점들을 쌍으로 연결하면 됩니다. 따라서 $\mathcal{O}(n\log n)$의 복잡도를 갖는 해법을 얻습니다.
포텐셜 문제. 행렬 $A[1 \ldots n][1 \ldots m]$이 주어졌을 때, 임의의 $i$와 $j$에 대해 $u[i] + v[j] \leq a[i][j]$를 만족하면서 배열 $u$와 $v$의 원소의 합이 최대가 되도록 하는 두 배열 $u[1 \ldots n]$과 $v[1 \ldots m]$을 찾아야 합니다.
헝가리안 알고리즘을 알고 있다면 이 문제의 해법은 어렵지 않습니다. 헝가리안 알고리즘이 바로 문제의 조건을 만족하는 그러한 포텐셜 $u, v$를 찾아 주기 때문입니다. 반면 헝가리안 알고리즘을 모른다면 이러한 문제를 푸는 것은 거의 불가능해 보입니다.

비고

이 문제는 할당 문제의 쌍대 문제라고도 불립니다. 할당의 총비용을 최소화하는 것은 포텐셜의 합을 최대화하는 것과 동치입니다.

할당 문제를 해결하기 위한 헝가리안 알고리즘¶

할당 문제의 정의¶

헝가리안 알고리즘¶

역사적 배경¶

$\mathcal{O}(n^4)$ 알고리즘¶

$\mathcal{O}(n^3)$ 알고리즘¶

헝가리안 알고리즘의 구현¶

연속 최단 경로 알고리즘과의 관계¶

문제 예시¶

참고 문헌¶

연습 문제¶