할당 문제(assignment problem)는 \(n\) 명의 노동자와 \(n\) 개의 작업이 주어지고, 각 노동자-작업 쌍마다 노동자를 작업에 할당할 때의 비용이 주어질 때, 최소의 비용으로 각 노동자를 작업에 하나씩 할당하는 방법을 찾는 문제입니다. 제 블로그에는 할당 문제와 이를 해결하는 알고리즘인 헝가리안 알고리즘(Hungarian algorithm)에 대해 정리한 글이 있습니다. 제 블로그에서 가장 인기가 있는 글이죠.
2019.08.07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm)
할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm)
이번 포스팅에서는 assignment problem과 Hungarian algorithm에 대해서 알아보겠습니다. 먼저 assignment problem이 어떤 것인지에 대해서 살펴보고, 이를 해결하는 방법을 알아보도록 하겠습니다. 인터넷을 찾
gazelle-and-cs.tistory.com
위 글에서는 헝가리안 알고리즘이 다항 시간에 수행된다는 것은 보이지 못했습니다. 대신 이후 다른 포스트에서 헝가리안 알고리즘이 네제곱 시간에 수행된다는 것을 보였죠.
2020.03.18 - [조합론적 최적화/Matching] - 헝가리안 알고리즘 시간 복잡도 분석
헝가리안 알고리즘 시간 복잡도 분석
지난번에 할당 문제와 헝가리안 알고리즘을 주제로 글을 작성하였습니다. 아래 링크를 참조하세요. 2019/08/07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian
gazelle-and-cs.tistory.com
위 글의 말미에서 저는 그 보다 빠른 시간에 수행될 수 있는지에 대한 질문을 드렸습니다. 그 답을 이번에 드리겠습니다. 이번 글의 주제는 할당 문제를 세제곱 시간에 해결하는 방법입니다.
문제 정의
이번 글에서 소개할 알고리즘을 이해하기 위해서는 할당 문제를 그래프 문제로 이해하는 것이 좋습니다. 우리에게는 방향이 없는 완전 이분 그래프(undirected complete bipartite graph) \(G = (I \cup J, E) \)와 간선의 비용 \(c : E \to \mathbb{Q} \)가 주어집니다. 여기서 \(I\)는 노동자의 집합에 \(J\)는 작업의 집합에 대응하며, 간선 \( (i, j) \in E \)의 비용 \(c(i, j)\)는 노동자 \(i\)를 작업 \(j\)에 할당했을 때 소모되는 비용을 나타냅니다. 이때, 노동자의 수와 작업의 개수는 둘 다 \(n\)으로 동일하다고 하겠습니다.
그래프 위에서 우리가 찾아야 할 것은 무엇일까요? 모든 노동자를 작업 하나씩에 중복 없이 할당하는 방법 중에서 가장 비용이 저렴한 것을 찾아야 하므로, \(G\) 위의 완벽 매칭(perfect matching) \( M \subseteq E \) 중 비용 \( c(M) := \sum_{e \in M} c(e) \)이 가장 저렴한 것을 찾으면 됩니다.
잔여 비용 (Residual Cost) & 음의 순환 (Negative Cycle)
매칭 문제를 해결할 때 가장 요긴하게 사용되는 도구는 바로 증가 경로(augmenting path)입니다. 어떤 매칭 \(M\)이 주어졌을 때, \(M\)의 간선에 인접하지 않은 노출된(exposed) 정점에서 시작하여 \(M\)에 속하지 않은 간선과 \(M\)에 속한 간선을 번갈아 따라가다 마지막에 다른 노출된 정점에서 끝나는 경로를 \(M\)에 대한 증가 경로 \(P\)라고 합니다. 증가 경로라고 불리는 이유는 \(P\)를 따라 \(M\)에 원래 들어 있지 않은 간선은 \(M\)에 넣고, 들어 있는 간선은 \(M\)에서 빼는 방식으로 얻은 \(M \oplus P\)는 \(M\)보다 간선이 하나 더 많은 매칭이 되기 때문입니다. 관련하여 자세한 사항은 다음 글에서 확인하시기 바랍니다.
2020.02.22 - [조합론적 최적화/Matching] - 호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm)
호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm)
엄청 오랜만에 포스팅을 합니다. 방학이 되면 시간이 나서 글을 좀 쓸 수 있을 줄 알았는데, 대학원생은 방학도 바쁘군요. 다행히 어느정도 일단락이 나서 이렇게 글을 쓸 수 있게 되었습니다.
gazelle-and-cs.tistory.com
이를 간선에 비용이 있는 경우로 확장해 봅시다. 증가 경로 \(P\)의 간선의 비용은 어떻게 설정하면 좋을까요? 원래 \(M\)에 속하지 않은 간선은 새로 들어가게 될 것이므로 원래 비용 그대로를 쓰면 될 것입니다. 반대로 \(M\)에 원래부터 속했던 간선은 \(M \oplus P\)에서는 없으므로 해당 비용을 빼 주어야 할 것입니다.
이 아이디어를 다음의 보조 그래프로 정형화 해보겠습니다. 입력 그래프 \( G=(I \cup J, E) \)와 간선 비용 \(c : E \to \mathbb{Q}\) 그리고 \(G\) 위의 (완벽하지 않을 수도 있는) 어떤 매칭 \(M\)에 대해서, 방향이 있는 그래프 \(G_M := (I \cup J \cup \{s, t\}, A_M)\)과 그 위의 간선 비용 \( c_M : A_M \to \mathbb{Q} \)을 다음과 같이 정의합니다.
- \(s\)와 \(t\)는 \(I\)와 \(J\)에 속하지 않은 새로운 정점들이다.
- \(M\)으로부터 노출된 정점 \(i \in I\)에 대해, \( \langle s, i \rangle \in A_M \)이며, 그 비용 \( c_M(s, i) = 0 \)이다.
- \(M\)으로부터 노출된 정점 \(j \in J\)에 대해, \( \langle j, t \rangle \in A_M \)이며, 그 비용 \(c_M(j, t) = 0\)이다.
- 모든 \( (i, j) \in E \setminus M \)에 대해, \( \langle i, j \rangle \in A_M \)이며, 그 비용 \( c_M (i, j) = c(i, j) \)이다.
- 모든 \( (i, j) \in M \)에 대해, \( \langle j, i \rangle \in A_M \)이며, 그 비용 \( c_M (j, i) = -c(i, j) \)이다.
이렇게 얻은 \(G_M\)은 잔여 그래프(residual graph), \(c_M\)은 잔여 비용(residual cost)라고 부르겠습니다.
잔여 그래프와 잔여 비용이 갖는 여러 흥미로운 성질들을 알아 보겠습니다. 먼저 잔여 그래프 위에서의 \(s\)에서 \(t\)까지의 경로가 주어졌을 때 거기서 \(s\)와 \(t\)를 제거하면 원래 그래프에서의 증가 경로에 대응합니다. 반대로 원래 그래프에서의 증가 경로에 \(s\)와 \(t\)를 양 끝에 붙이고 올바르게 방향을 부여하면 잔여 그래프 위에서의 \(s\)에서 \(t\)까지의 경로가 되죠. 따라서 둘 사이에는 일대일 대응 관계가 성립합니다. 아래에서는 그냥 서로 같은 것처럼 취급하겠습니다.
또한 어떤 매칭과 그에 대한 증가 경로가 주어졌을 때, 우리는 이 경로를 적용하여 얻을 새로운 매칭의 비용을 잔여 비용을 활용해 다음과 같이 구할 수 있습니다. 증명은 간단하므로 생략합니다.
정리 1. 증가 경로와 잔여 비용
어떤 매칭 \(M\)과 그에 대한 증가 경로 \(P\)에 대하여, \( M \oplus P \)는 \[ c(M \oplus P) = c(M) + c_M(P) \]를 만족한다.
마지막으로 잔여 그래프와 잔여 비용은 완벽 매칭이 최적해인지를 판별하는 데도 요긴합니다. 어떤 완벽 매칭 \(M\)에 대해, \( G_M, c_M \)에 음의 비용을 갖는 순환, 즉 \( c_M(C) < 0 \)인 순환 \(C\)가 있다고 생각해 보겠습니다. 이는 원래 그래프에서 \(M\)에 속한 간선과 \(M\)에 속하지 않은 간선이 번갈아 나오는 순환이며, 따라서 \(C\)를 따라 \(M\)에 넣고 빼고를 반복하여 얻은 \(M \oplus C\)는 새로운 완벽 매칭이 됩니다. 이 매칭의 비용은 얼마일까요? 어렵지 않게 \[ c(M \oplus C) = c(M) + c_M(C) < c(M) \]임을 알 수 있으며, 따라서 \(M\)이 가장 비용이 저렴한 완벽 매칭이 아니라는 증거가 됩니다. 그리고 사실, 이 조건은 필요충분조건입니다.
정리 2. 완벽 매칭이 최적해일 필요충분조건
어떤 완벽 매칭 \(M\)이 가장 비용이 저렴한 완벽 매칭일 필요충분조건은 \( c_M(C) < 0 \)인 \(C\)가 \(G_M\)에 존재하지 않는 것이다.
[증명] 앞에서 음의 순환 \(C\)가 존재하면 \(M\)이 최적해가 아니라는 것을 보였습니다. 따라서 \(M\)이 최적해가 아닐 때 \(c_M(C) < 0\)인 순환 \(C\)가 \(G_M\)에 존재함을 보이면 증명이 완료됩니다. \(M\)이 최적해가 아니라고 하였으므로 \(M^* \neq M\)를 최적해라고 하겠습니다. 이제 \( M \)에만 있거나 \(M^*\)에만 있는 간선들, 즉 \( (M \setminus M^*) \cup (M^* \setminus M) \)을 갖고 옵시다. \(M\)과 \(M^*\)가 둘다 완벽 매칭이므로 이는 여러 순환들의 합집합으로 이루어지게 됩니다. 그 중에서는 분명 \( c_M(C) < 0 \)인 순환 \(C\)가 존재하는데, 그 이유는 만약 그렇지 않다면 \(M\)이 \(M^*\)보다 비싸지 않게 되기 때문입니다. ■
위 정리들을 통해 다음과 같은 간단한 알고리즘을 생각해 볼 수 있습니다.
처음에 \(M \gets \emptyset\)으로 시작한다. 매번 \(M\)에 대한 특정한 증가 경로 \(P\)를 찾고 \( M \gets M \oplus P \)를 수행한다.
여기서 만약 알고리즘이 진행되는 내내 \(G_M\)에 음의 순환이 존재하지 않는다면, 정리 2를 통해 이 알고리즘은 최종적으로 최적해를 출력할 것입니다.
그럼 매번 어떤 증가 경로를 찾아야 할까요? 가장 쉽게 생각해 볼 수 있는 경로는 바로 \( G_M \)에서의 최단 경로(shortest path)입니다. 그리고 흥미롭게도 최단 경로를 찾아서 적용하면 실제로 위 알고리즘이 성립합니다. 다만 여기에는 한 가지 큰 문제점이 있는데 바로 \(c_M\)이 음수가 될 수 있다는 점입니다. 이것이 문제점인 이유는 다음과 같습니다.
- 최단 경로를 찾을 때 벨만-포드 알고리즘(Bellman-Ford algorithm)을 써야 합니다. 이는 수행 시간이 \( O(|V||E|) \)로, \(n\)으로 표현하면 \( O(n^3) \)입니다. 우리는 위 작업을 총 \(n\)번 수행해야 하므로, 알고리즘의 총 수행 시간은 \(O(n^4)\)이 됩니다.
- 또한, \(c_M\)이 음수가 될 수 있는 상황에서 음의 순환이 존재하지 않음을 보이는 것은 쉽지 않습니다.
이에 대한 해결책은 하나입니다. 어떤 방식으로든 \( c_M \)이 음이 아닌 수만을 갖도록 만드는 것이죠. 그러면 위 문제점을 아래와 같이 모두 해결할 수 있습니다.
- 최단 경로를 찾을 때 다익스트라의 알고리즘(Dijkstra's algorithm)을 사용할 수 있으며, 이는 \(O(|V|^2) = O(n^2) \)의 수행 시간을 갖습니다. 따라서 알고리즘의 전체 수행 시간은 \(O(n^3)\)이 됩니다.
- 모든 비용이 음이 아니면 음의 순환이 존재하지 않는다는 것은 자명합니다.
과연 어떻게 하면 \(c_M\)을 음이 아닌 수로 만들 수 있을까요? 이는 다음 절에서 알아 보겠습니다.
참고로 벨만-포드 알고리즘이나 다익스트라의 알고리즘에 대해서 궁금하신 분들은 아래 제가 예전에 적은 포스트를 참고하시기 바랍니다. 사실 다익스트라의 알고리즘은 이번 글을 적기 위해서 적었답니다.
최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman-Ford Algorithm)
자동차를 타고 서울에서 부산까지 여행을 떠난다고 생각해 봅시다. 일분일초라도 여행을 더 즐기기 위해서는 빨리 목적지에 도달하는 것이 좋겠죠. 그러려면 어떤 경로를 따라 자동차를 운전해
gazelle-and-cs.tistory.com
2021.10.09 - [조합론적 최적화/Shortest path] - 다익스트라의 알고리즘 (Dijkstra's Algorithm)
다익스트라의 알고리즘 (Dijkstra's Algorithm)
최단 경로 문제(shortest path problem)는 가장 유명한 조합론적 최적화 문제 중 하나로, 이름에서 유추할 수 있듯이 다양한 분야에서 널리 활용되는 문제입니다. 지난 포스트에서는 이 문제를 정확히
gazelle-and-cs.tistory.com
위 알고리즘들은 출발지가 주어졌을 때, 거기서부터 도달 가능한 모든 정점들까지의 최단 경로 및 그 비용을 구하는 알고리즘들입니다. 이를 구할 수 있는 이유는 최단 경로가 아래와 같은 특별한 구조적인 특징을 갖고 있기 때문입니다. 이 정리는 아래에서도 요긴하게 활용됩니다.
정리 3. 최단 경로들의 관계
임의의 방향 그래프와 간선 비용, 그리고 출발지 \(s\)가 주어졌다고 하자. 임의의 정점 \(v\)에 대해, \( P = \langle s, \cdots, u, v \rangle \)가 \(s\)에서 \(v\)로 향하는 최단 경로라고 하자. 그러면 \(P\)에서 마지막 \(v\)를 제거한 경로는 \(s\)에서 \(u\)까지 향하는 최단 경로이다.
증명은 위 포스트에서 찾아 보실 수 있습니다.
환산 비용 (Reduced Cost)
헝가리안 알고리즘이 어떻게 동작했는지 돌이켜 봅시다. 어느 한 정점에 인접한 간선의 비용마다 동일한 값을 더하거나 빼면 모든 매칭의 비용이 동일하게 증가하거나 감소하기 때문에 최적해에 영향을 주지 않았습니다. 이 성질을 이용해 각 정점마다 적절한 값을 더하거나 빼서 모든 비용이 음이 아니게 만들고, 그중 0의 비용을 갖는 간선으로만 완벽 매칭을 찾는 것이 알고리즘의 요지였습니다.
이번에도 이 아이디어를 이용해 볼까 합니다. 각 정점 \(v \in I \cup J\)마다, 적절한 \( p(v) \)를 두어 \(v\)에 인접한 간선의 비용에 모두 \(p(v)\)를 빼주는 것이죠. 다시 말해, \( p : I \cup J \to \mathbb{Q} \)가 주어졌을 때, 각 간선 \( (i, j) \in E\)의 비용을 \[ c^p(i, j) := c(i, j) - p(i) - p(j)\]로 설정하는 것입니다. 참고로 \(p\)는 음수가 될 수도 있습니다. 이 비용을 환산 비용(reduced cost)이라고 부르겠습니다.
환산 비용도 간선의 비용이므로 어떤 매칭 \(M\)에 대해서 잔여 그래프와 잔여 비용을 생각할 수 있습니다. 이때 그래프는 \(G_M\)으로 동일하나, 잔여 비용은 \( c^p_M \)으로 \( c_M \)과는 다를 것입니다. 그런데 놀랍게도 잔여 환산 비용과 원래의 잔여 비용 사이에는 다음과 같은 흥미로운 성질이 있습니다.
정리 4. 잔여 비용과 잔여 환산 비용의 관계
어떤 매칭 \(M\)이 주어졌다고 하자. 그러면 임의의 \(p : I \cup J \to \mathbb{Q}\)에 대해, 잔여 그래프 \(G_M\)의 어떤 순환 \(C\)는 원래의 잔여 비용에 대해서나 잔여 환산 비용에 대해서나 동일한 비용을 갖는다. 즉, \(c_M(C) = c^p_M(C)\)이다.
[증명] 잔여 그래프 \(G_M\)의 순환 \(C\)는 반드시 \(M\)에 속한 간선과 \(M\)에 속하지 않은 간선이 번갈아 나타나는 형태입니다. 이때, \( \langle i, j \rangle \in A_M \setminus M \)에 대해서는 \[ c^p_M(i, j) = c^p(i, j) = c(i, j) - p(i) - p(j) \]의 비용을 가질 것이며, \( \langle j, i \rangle \in M\)에 대해서는 \[ c^p_M (j, i) = - c^p(i, j) = - c(i, j) + p(i) + p(j) \]의 비용을 갖습니다. 따라서 \(c^p_M\)에 대한 \(C\)의 간선의 비용을 모두 더하면 \( p(i) \)와 \( p(j) \)들은 모두 서로 상쇄되고, \[ \sum_{\langle i, j \rangle \in C \setminus M} c(i, j) + \sum_{\langle j, i \rangle \in C \cap M} (- c(i, j)) = \sum_{e \in C} c_M(e) = c_M(C) \]이 되어 명제가 성립합니다. ■
이를 통해 만약 우리가 \(p\)를 적절히 조절하여 매번 \(c^p_M\)이 모두 음이 아닌 수로만 이루어지도록 만들 수 있다면, 임의의 순환은 잔여 환산 비용을 기준으로 하나 잔여 비용을 기준으로 하나 동일한 비용을 가질 것이므로 정리 2에 의거하여 이전 절에서 제시한 알고리즘을 완성할 수 있게 됩니다.
그러면 매칭 \(M\)이 주어졌을 때, 어떤 \(p\)를 얻어야 할까요? 기존의 헝가리안 알고리즘을 생각해 보면 환산 비용 \(c^p\) 자체는 음이 아닌 수가 되는 것이 좋겠습니다. 또한 잔여 환산 비용 \(c^p_M\)도 모두 음이 아니기를 바랍니다. 이를 모두 만족하는 \(p\)는 아래뿐입니다.
- \( (i, j) \not\in M \)에 대해서는 \( c^p(i, j) \geq 0 \)이다.
- \( (i, j) \in M \)에 대해서는 \( c^p(i, j) = 0 \)이다.
그러면 \( c^p \)와 \( c^p_M \) 모두 음이 아닌 수로만 이루어진다는 것을 확인할 수 있습니다.
환산 비용 유지하기
앞에서 배운 내용을 토대로 알고리즘을 다음과 같이 수정해 보겠습니다.
처음에 \(M \gets \emptyset \)로 하고, 적절하게 \(p\)를 설정한다. 매번 \(G_M, c^p_M\)의 최단 증가 경로 \(P\)를 찾아 \( M \gets M \oplus P \)를 수행하고, \(p\)를 적절하게 수정한다.
만약 \(p\)가 앞에서 살펴본 조건을 모두 만족한다면, 이 알고리즘은 최종적으로 최적해를 출력할 것이고, 매번 증가 경로를 찾을 때 다익스트라의 알고리즘을 사용할 수 있어서 \(O(n^3)\)의 시간에 수행될 것입니다.
먼저 알고리즘이 시작할 때의 \(p\)를 알아 봅시다. 시작할 때에는 \(M = \emptyset \)이므로, 그냥 모든 간선 \( (i, j) \in E \)에 대해, \( c^p(i, j) \geq 0 \)을 만족하면 됩니다. 이를 하는 방법은 여러 가지가 있겠으나, 본문에서는 가장 간단한 방법 중 하나인
- 모든 노동자 정점 \(i \in I \)에 대해, \( p(i) = 0 \)
- 모든 작업 정점 \( j \in J \)에 대해, \( p(j) = \min_{i \in I} c(i, j) \)
로 설정하겠습니다.
따라서 남은 것은 알고리즘이 언젠가 어떤 \( M \)과 적절한 \(p\)를 유지하고 있을 때, \(G_M, c^p_M\) 상의 최단 경로 \(P\)를 찾아 적용한 다음의 매칭 \( M \oplus P \)에 대해 \(p\)를 적절하게 수정하는 것입니다. 얼핏 보기에는 가능한가 싶지만, 놀랍게도 가능합니다. 이를 먼저 예시와 함께 알아 보도록 하죠.
그림 9의 상황에서 \(G_M, c^p_M\) 위 \(s\)에서 \(t\)까지의 최단 경로는 0의 비용을 갖는 \(\langle s, u, x ,t \rangle\)입니다. 이를 따라 \(M\)을 갱신하면 \( M = \{ (u, x) \} \)가 됩니다. 원래 \(c^p(u, x) = 0\)이었으므로 여전히 \(p\)는 원하는 조건을 만족합니다.
다음 단계에서 찾는 최단 증가 경로 \(P\)는 그림 10과 같이 \( \langle s, w, y, t \rangle \)입니다. 따라서 이를 적용하면 \( M = \{ (u, x), (w, y) \} \)가 됩니다. 일단 동일한 \(p\)에 대해서 \(c^p_M\)은 다음 그림과 같습니다.
그러면 \( c^p(w, y) = 1 \)이라서 우리가 원하는 환산 비용의 상태가 아닙니다. 따라서 이를 \( c^p(w, y) = 0 \)이 되도록 \(p\)를 갱신해 주어야 합니다. 어떻게 하면 될까요?
일단 \( c^p(w, y) = c(w, y) - p(w) - p(y) \)이므로 \( p(w) \)나 \( p(y) \)의 값을 1만큼 증가시켜 주어야 합니다. 한번 \( p(y) \)의 값을 1 증가시켜 보죠. 그러면 이번에는 \(c^p(u, y)\)가 문제가 됩니다. 원래 \( c^p(u, y) = 0 \)이었는데, \(p(y)\)가 1 증가하였으므로 갱신 후에는 \( c^p(u, y) = -1 \)이 되기 때문이죠. 따라서 대신 \( p(u) \)의 값을 1 감소시켜 보겠습니다. 이번에는 무엇이 문제가 될까요? \((u, x) \in M\)이므로 계속 \( c^p(u, x) = 0 \)이기를 바라는데 \( p(u) \)가 1 감소하므로 갱신 후에는 \( c^p(u, x) = 1 \)이 되어 버립니다.
이렇게 조금씩 바꿔서 원하는 \(p\)로 갱신하는 방법은 그리 좋아 보이지 않습니다. 어떻게 하면 될까요? 사실 최단 경로 문제를 해결하면 \(s\)에서 \(t\)까지의 최단 경로뿐 아니라 \(s\)에서 다른 모든 정점까지의 최단 경로의 비용을 구할 수 있습니다. 각 정점 \(v \in I \cup J\)에 대해서 \( d(v) \)를 \(s\)에서 \(v\)까지의 최단 경로의 비용이라고 하겠습니다. 그러면, 노동자 \( i \in I \)에 대해서는 \(p(i)\)에서 \( d(i) \)를 빼고, 작업 \( j \in J \)에 대해서는 \(p(j)\)에서 \( d(j) \)를 더하는 것으로 우리가 원하는 \(p\)로 갱신할 수 있게 됩니다.
이런 놀라운 성질에 대한 엄밀한 증명은 아래와 같습니다.
정리 5. 환산 비용 수정 방법
어떤 매칭 \(M\)과 \(p\)가
- 모든 \( (i, j) \not\in M\)에 대해서는 \( c^p(i, j) \geq 0\),
- 모든 \( (i, j) \in M \)에 대해서는 \( c^p(i, j) = 0 \)
을 만족한다고 하자. 각 정점 \( v \in I \cup J \)에 대해서 \( d(v) \)를 \( G_M \)에서 \( c^p_M \)의 비용으로 \(s\)에서 \(v\)까지의 최단 경로의 비용이라고 하고, \(p' : I \cup J \to \mathbb{Q}\)를 다음과 같이 정의하자.
- 모든 노동자 \(i \in I\)에 대해서, \( p'(i) := p(i) - d(i) \)
- 모든 작업 \( j \in J \)에 대해서, \( p'(j) := p(j) + d(j) \)
그러면 \( G_M, c^p_M \)의 최단 증가 경로 \(P\)에 대해 \(M' := M \oplus P\)는
- 모든 \((i,j) \not\in M'\)에 대해서는 \(c^{p'}(i, j) \geq 0\),
- 모든 \( (i,j) \in M' \)에 대해서는 \( c^{p'}(i, j) = 0 \)
을 만족한다.
[증명] 간선을 총 네 경우로 나누어서 생각해 봅시다.
경우 1. \( (i, j) \in P \setminus M \). 이 간선은 \(M'\)에 새로 들어 오는 간선입니다. 따라서 \( c^{p'}(i, j) = 0 \)을 만족해야 하죠. \( (i, j) \not\in M\)이므로, \(\langle i, j \rangle \in A_M\)입니다. 이때, \(P\)는 \(c^p_M\)을 비용으로 \(s\)에서 \(t\)까지 향하는 최단 경로이므로 정리 3을 통해 우리는 \[ d(j) = d(i) + c^p_M(i, j) = d(i) + c(i, j) - p(i) - p(j) \]임을 알 수 있습니다. 위 식을 정리하면 \[ 0 = c(i, j) - (p(i) - d(i)) - (p(j) + d(j)) = c(i, j) - p'(i) - p'(j) = c^{p'}(i, j) \]라는 것을 이끌어 낼 수 있습니다.
경우 2. \( (i, j) \in P \cap M \). 이 간선은 원래는 \(M\)에 있었지만, \(M'\)에서는 나가게 되는 간선입니다. 따라서 \( c^{p'}(i, j) \geq 0 \)이기만 하면 됩니다. \( (i, j) \in M \)이므로, \( \langle j, i \rangle \in A_M \)이었으며, 그 잔여 환산 비용 \( c^p_M(j, i) = 0 \)입니다. \(P\)는 \(s\)에서 \(t\)까지의 최단 비용이므로, 똑같이 정리 3을 통해 \[ d(i) = d(j) + c^p_M(j, i) = d(j) \]가 됩니다. 따라서 \[ c^{p'}(i, j) = c(i, j) - p'(i) - p'(j) = c(i, j) - (p(i) - d(i)) - (p(j) + d(j)) = c^p(i, j) = 0 \]이 되므로 명제가 성립합니다.
경우 3. \( (i, j) \in E \setminus (P \cup M) \). 이 간선은 증가 경로 적용 이후에도 계속 매칭에 들어 오지 않는 간선으로, \( c^{p'}(i, j) \geq 0 \)을 만족하면 됩니다. \( (i, j) \not\in M \)이었으므로 \( \langle i, j \rangle \in A_M \)이고, \(s\)에서 \(i\)를 거쳐 \(j\)로 향하는 경로도 \(j\)까지 가는 경로 중 하나이므로, \[ d(j) \leq d(i) + c^p_M(i, j) = d(i) + c(i, j) - p(i) - p(j) \]임을 알 수 있습니다. 이를 정리하면, \[ 0 \leq c(i, j) - (p(i) - d(i)) - (p(j) + d(j)) = c^{p'}(i, j) \]임을 얻을 수 있습니다.
경우 4. \( (i, j) \in M \setminus P \). 이 간선은 증가 경로 적용 이후에도 계속 매칭에 남아 있는 간선으로, \( c^{p'}(i, j) = 0 \)을 만족해야 합니다. \( (i, j) \in M \)이므로 \( \langle j, i \rangle \in A_M \)입니다. 여기서 \( i \)에 들어오는 간선은 \( \langle j, i \rangle \)뿐이라는 것을 확인하시기 바랍니다. 따라서 \(s\)에서 \( i \)에 도달하기 위해서는 반드시 \( j \)를 지나야 합니다. 그러므로 \( d(i) = d(j) + c^p_M(j, i) = d(j) \)임을 알 수 있습니다. 경로 2와 마찬가지로 \[ c^{p'}(i, j) = c(i, j) - p'(i) - p'(j) = c(i, j) - p(i) - p(j) = c^p(i, j) = 0\]이라는 사실을 알 수 있습니다. ■
정리 5를 통해 우리는 알고리즘을 다음과 같이 완성할 수 있습니다.
알고리즘 1. An improved Hungarian algorithm
입력: 완전 이분 그래프 \(G = (I \cup J, E) \), 간선 비용 \(c : E \to \mathbb{Q}\)
출력: 가장 비용이 저렴한 완벽 매칭
- \(M \gets \emptyset \)
- 모든 \(i \in I\)에 대해, \(p(i) \gets 0 \)
- 모든 \(j \in J \)에 대해, \( p(j) \gets \min_{i \in I} c(i, j) \)
- 아래를 \(n = |I| = |J|\) 번 반복한다.
- 잔여 그래프 \(G_M\)과 잔여 환산 비용 \(c^p_M\)을 만든다.
- 다익스트라의 알고리즘으로 \(G_M, c^p_M\) 위 \(s\)에서 \(t\)까지의 최단 증가 경로 \(P\)와 각 정점 \(v \in I \cup J\)로 향하는 최단 경로의 비용 \(d(v)\)를 구한다.
- \( M \gets M \oplus P \)
- 모든 \( i \in I \)에 대해, \( p(i) \gets p(i) - d(i) \)
- 모든 \( j \in J \)에 대해, \( p(j) \gets p(j) + d(j) \)
- \(M\)을 반환한다.
앞에서 다익스트라의 알고리즘은 \(O(n^2)\)에 수행된다 했습니다. 단계 4의 세부 단계 모두 \( O(n^2) \)에 수행 가능하고, 단계 3은 \(O(n^2)\) 시간에 가능합니다. 따라서 위 알고리즘은 \(O(n^3)\)에 동작합니다.
마치며
이번 포스트에서는 헝가리안 알고리즘이 세제곱 시간에 수행되도록 만드는 방법에 대해서 알아 보았습니다. 이를 공부하면서 동시에 다익스트라의 알고리즘도 잘 알게 되어 기쁩니다. 제가 보기에는 네제곱 수행 시간을 갖는 헝가리안 알고리즘이 세제곱 수행 시간을 갖는 것으로 잘못 알려진 것 같은데, 이 포스트가 해당 내용들을 바로 잡아 주기를 바랍니다. (혹시나 기존 알고리즘이 원래 세제곱 수행 시간을 가지는 것이라면 댓글로 알려 주시기를 부탁 드립니다. 제가 분석을 못한 것일 수도 있죠)
사실 이 알고리즘은 훨씬 큰 범주의 문제로 확장 가능합니다. 바로 최소 비용 최대 흐름 문제(minimum cost maximum flow problem)입니다. 사실 매칭은 최대 흐름 문제와 많은 관련이 있으므로 둘의 연관성을 유추하기는 그리 어렵지 않은데요. 이 알고리즘이 어째서 해당 문제와 큰 관련이 있는지는 다음에 알아 보겠습니다.
읽어 주셔서 고맙습니다.
참조
[1] Jon Kleinberg and Eva Tardos. Algorithm design. Pearson Education, 2013.
'조합론적 최적화 > Matching' 카테고리의 다른 글
| 안정 매칭 (Stable Matching) (2) | 2023.02.25 |
|---|---|
| 경제학으로 해석한 헝가리안 알고리즘 (0) | 2021.12.25 |
| 텃의 정리 (Tutte's Theorem) (0) | 2020.10.10 |
| 헝가리안 알고리즘 시간 복잡도 분석 (7) | 2020.03.18 |
| 호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm) (9) | 2020.02.22 |
