외판원 순회
Problem
https://www.acmicpc.net/problem/2098
Summary
한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로
중 가장 적은 비용을 들이는 여행 경로구하기 도시의 수 N (2<=N<=16)
Idea
각 도시를 전체 순회해보는 방법은 N! 가지가 된다. 10!는3628800 이며 11!는 39916800이다.
전체 탐색
static private void TSP(int curr, ArrayList<Integer> path, int sum) {
if (path.size() == N) {
int ret = W[curr][path.get(0)];
if (ret == 0) {
return;
}
sum += ret;
if (min > sum) {
min = sum;
}
return;
}
for (int i = 0; i < N; i++) {
if (curr == i || W[curr][i] == 0) {
continue;
}
if (visited[i] == false) {
visited[i] = true;
path.add(i);
TSP(i, path, sum + W[curr][i]);
visited[i] = false;
path.remove(path.size()-1);
}
}
}
DP
방문도시 1->2->3->4->5 와 1->2->3->5->4 로 순회 시 1->2->3은 이미 방문했던 길로 중복 체크 될 수 있다
f(N (시작점)에서 출발해서 모든 도시를 방문할 때 드는 최소 비용.
f(N, {N-1,N-2….1}) = cost(N,N-1) + f(N-1, {N-2,N-3,….1})
dp[1][0000 1110(=14)] = f(1, {2,3,4}) ==> 도시 1에서 2,3,4를 순회하는 최소비용
dp[2][0000 1101(=13)] = f(2, {1,3,4}) ==> 도시 2에서 1,3,4를 순회하는 최소비용
visited 표현 시 bit operation 활용
- 전체집합 (1«20) -1
- p번 원소 추가 set |= (1«p)
- p번 원소 확인: p번 원소를 켜있는지 확인 set & (1«p)
- p번 원소 삭제: p번 원소를 끈다 set &= ~(1«p)
- p번 원소 토글: p번 원소가 켜있으면 끄고, 꺼있으면 킨다 set ^= (1«p)
int min = Integer.MAX_VALUE;
for (int i = 1 ; i <= N; i++) {
end = i;
min = Math.min(min, TSP(i, 1 << (i-1)));
}
static private int TSP(int curr, int visited) {
if (visited == (1<< (N+1)) - 1) {
return W[curr][end];
}
int ret = 0;
ret = cached[curr][visited];
if (ret != 0) {
return ret;
}
ret = Integer.MAX;
for (int i = 1; i <= N; i++) {
if (curr == i || W[curr][i] == 0) {
continue;
}
if ((visited & (1 << i)) > 0) {
continue;
}
//ret = Math.min(ret, TSP(i, visited | 1 << i) + W[curr][i]);
if (ret > TSP(i, visited | 1 << i) + W[curr][i]) {
ret = TSP(i, visited | 1 << i) + W[curr][i];
}
}
cached[curr][visited] = ret;
return cached[curr][visited];
}
부분 문제 수: N(노드수) * 2^N (방문체크), tsp 내에서의 반복 = N^2 * 2^N