최소 비용 흐름을 이용한 할당 문제 풀이¶
할당 문제는 서로 동치인 두 가지 형태로 서술할 수 있습니다.
- 정사각 행렬 $A[1..N, 1..N]$이 주어질 때, 각 행과 각 열에서 정확히 하나의 원소가 선택되고 선택된 원소들의 값의 합이 최소가 되도록 $N$개의 원소를 선택해야 합니다.
- $N$개의 주문과 $N$대의 기계가 있습니다. 각 주문마다 각 기계에서 제조할 때의 비용이 알려져 있습니다. 각 기계에서는 하나의 주문만 수행할 수 있습니다. 총비용이 최소가 되도록 모든 주문을 기계에 할당해야 합니다.
여기서는 최소 비용 흐름(min-cost-flow)을 찾는 알고리즘을 바탕으로 할당 문제를 $\mathcal{O}(N^3)$에 푸는 방법을 살펴보겠습니다.
설명¶
이분 네트워크를 구성합시다. 소스 $S$와 싱크 $T$가 있고, 첫 번째 부분에는 $N$개의 정점(행렬의 행, 즉 주문에 해당)이 있으며, 두 번째 부분에도 $N$개의 정점(행렬의 열, 즉 기계에 해당)이 있습니다. 첫 번째 집합의 각 정점 $i$와 두 번째 집합의 각 정점 $j$ 사이에 용량이 1이고 비용이 $A_{ij}$인 간선을 긋습니다. 소스 $S$에서 첫 번째 집합의 모든 정점 $i$로 용량이 1이고 비용이 0인 간선을 긋습니다. 두 번째 집합의 각 정점 $j$에서 싱크 $T$로 용량이 1이고 비용이 0인 간선을 긋습니다.
이렇게 만든 네트워크에서 최소 비용 최대 흐름을 구합니다. 당연히 흐름의 값은 $N$이 됩니다. 또한 첫 번째 부분의 각 정점 $i$에 대해 흐름 $F_{ij}$ = 1인 두 번째 부분의 정점 $j$가 정확히 하나 존재합니다. 결국 이것은 첫 번째 부분의 정점들과 두 번째 부분의 정점들 사이의 일대일 대응이며, 이것이 곧 문제의 해입니다(찾은 흐름의 비용이 최소이므로 선택된 간선들의 비용 합도 가능한 한 가장 작으며, 이것이 최적성의 기준입니다).
이 할당 문제 풀이의 복잡도는 최소 비용 최대 흐름을 찾는 데 사용하는 알고리즘에 따라 달라집니다. Dijkstra를 사용하면 복잡도가 $\mathcal{O}(N^3)$이 되고, Bellman-Ford를 사용하면 $\mathcal{O}(N^4)$이 됩니다. 흐름의 크기가 $O(N)$이고 Dijkstra 알고리즘의 각 반복은 $O(N^2)$에 수행할 수 있는 반면, Bellman-Ford는 $O(N^3)$이 걸리기 때문입니다.
구현¶
여기에 제시된 구현은 길며, 아마 상당히 줄일 수 있을 것입니다. 이 구현은 최단 경로를 찾는 데 SPFA 알고리즘을 사용합니다.
const int INF = 1000 * 1000 * 1000;
vector<int> assignment(vector<vector<int>> a) {
int n = a.size();
int m = n * 2 + 2;
vector<vector<int>> f(m, vector<int>(m));
int s = m - 2, t = m - 1;
int cost = 0;
while (true) {
vector<int> dist(m, INF);
vector<int> p(m);
vector<bool> inq(m, false);
queue<int> q;
dist[s] = 0;
p[s] = -1;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
inq[v] = false;
if (v == s) {
for (int i = 0; i < n; ++i) {
if (f[s][i] == 0) {
dist[i] = 0;
p[i] = s;
inq[i] = true;
q.push(i);
}
}
} else {
if (v < n) {
for (int j = n; j < n + n; ++j) {
if (f[v][j] < 1 && dist[j] > dist[v] + a[v][j - n]) {
dist[j] = dist[v] + a[v][j - n];
p[j] = v;
if (!inq[j]) {
q.push(j);
inq[j] = true;
}
}
}
} else {
for (int j = 0; j < n; ++j) {
if (f[v][j] < 0 && dist[j] > dist[v] - a[j][v - n]) {
dist[j] = dist[v] - a[j][v - n];
p[j] = v;
if (!inq[j]) {
q.push(j);
inq[j] = true;
}
}
}
}
}
}
int curcost = INF;
for (int i = n; i < n + n; ++i) {
if (f[i][t] == 0 && dist[i] < curcost) {
curcost = dist[i];
p[t] = i;
}
}
if (curcost == INF)
break;
cost += curcost;
for (int cur = t; cur != -1; cur = p[cur]) {
int prev = p[cur];
if (prev != -1)
f[cur][prev] = -(f[prev][cur] = 1);
}
}
vector<int> answer(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (f[i][j + n] == 1)
answer[i] = j;
}
}
return answer;
}