https://www.acmicpc.net/problem/2098
NP-hard로 알려진 문제다. 정의는 다음과 같다.
Input: An nxn size matrix
Output: A cyclic permutation that minimizes where π is a cyclic permutation, π: {1, ... ,n} -> {1, ... ,n}.
즉 n개의 도시를 순회할 때, 비용의 총합이 최소가 되는 경로를 찾는 문제다. Hamiltotion cycle을 TSP의 threshold version problem으로 reduce하여 TSP가 NP-hard임을 증명할 수 있다.
TSP의 특수한 케이스인 metric TSP의 경우, 1.5-approximation algorithm을 가지고 있다. 해당 알고리즘에 대해서는 추후 기회가 된다면 포스팅할 것이다.
풀이 방법
다시 문제로 돌아가보자. TSP는 NP-hard이므로 polynomial time 안에 해결할 수 없지만, 조금이라도 나은 시간복잡도를 가지기 위해 dynamic programming을 이용할 수 있다. Subproblem을 생각해보자. 현재까지 방문한 도시가 같고, 마지막으로 방문한 도시가 같다면 현재 위치와 앞으로 방문해야하는 도시가 같다. 즉, dp를 위한 array는 아래와 같다.
DP[most recently visited city #][cities already visited]
현재까지 방문한 도시들을 index로 사용하려면 bitmasking을 이용해야한다. 문제 조건에서 2<=N<=16이기 때문에 16개의 도시를 모두 표시해도 2^17 - 1로, int형 변수 범위 내에 들어오기 때문에 가능하다.
Recursion으로 구현하더라도 N이 최대 16이므로 recursive depth 또한 최대 16이기 때문에 stack overflow도 발생하지 않는다.
시간복잡도
O(n^2 2^n)이다. 총 subproblem의 개수가 n 2^n개이고(array DP의 크기), 각 subproblem에서 O(n)의 loop를 가지기 때문이다.
Naive approach
모든 경우에 대해 단순히 계산한다면, O(n!)의 시간복잡도를 가진다.
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int W[16][16];
int DP[16][1 << 16];
int visited_all;
#define MAXDIST 16 * 1000000 + 1
int TSP(int last, int visited) {
if (visited == visited_all) {
if (W[last][0] != 0)
return W[last][0];
else
return MAXDIST;
}
if (DP[last][visited] != 0) {
return DP[last][visited];
}
int minDist = MAXDIST;
for (int next = 0; next < n; next++) {
if (!((visited >> next) & 1) && W[last][next] != 0)
minDist = min(TSP(next, (1 << next) | visited) + W[last][next], minDist);
}
DP[last][visited] = minDist;
return minDist;
}
int main(void) {
cin >> n;
visited_all = (1 << n) - 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> W[i][j];
}
}
cout << TSP(0, 1) << endl;
return 0;
}