백준 2098번 외판원 순회

https://www.acmicpc.net/problem/2098

TSP (Traveling Salesman Problem)

NP-hard로 알려진 문제다. 정의는 다음과 같다.

Input: An nxn size matrix
Output: A cyclic permutation that minimizes $c(π) = \sum_{i=1}^{n}d_{i, π(i)}$ 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;
}