외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 4 35 #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int INF = 987654321;
int N, W[16][16], dp[16][1 << 16];
int TSP(int cur, int visited)
{
if(visited == (1 << N) - 1){ // 모든 마을을 방문했으면
if(W[cur][0] == 0) return INF; // 출발했던 도시로 갈 수 없으면 무한을 리턴
else return W[cur][0];
}
int dst = dp[cur][visited];
if(dst != -1) return dst; // 메모제이션
dst = INF;
for(int i=0; i<N; i++){
if(visited & (1 << i) || W[cur][i] == 0) continue; // 방문했던 도시이거나 갈 수 없으면
dst = min(dst, TSP(i, visited | 1 << i) + W[cur][i]); // 다음 도시로 가는 거리를 더해 업데이트 해줌
}
return dp[cur][visited] = dst;
}
int main(void)
{
scanf("%d", &N);
for(int i=0; i< N; i++){
for(int j=0; j<N; j++){
scanf("%d", &W[i][j]);
}
}
memset(dp, -1, sizeof(dp));
printf("%d\n", TSP(0,1));
return 0;
}백준 2098번 문제 외판원 순회
문제
computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다.
여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.
1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다)
이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로
돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다.
(맨 마지막에 여행을
출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데,
가장 적은 비용을 들이는 여행 계획을 세우고자 한다.
각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다.
W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다.
즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다.
경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.
N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.입력
0 10 15 20
5 0 9 10
6 13 0 12
8 8
9 0 출력
코드
풀이
오랜만에 알고리즘 업데이트 ~~ 개인적으로 어려웠던 문제이다.
마을의 방문을 표시하기 위해 비트마스킹을 사용한다.
1번 마을과 4번 마을을 방문했으면 10001
3번마을과 2번마을을 방문했으면 110
이런식으로 비트로 표현해준다. visited == (1 << N) - 1 이 구문은 모든
마을을 방문했을 때를 표시한다.
visited & (1 << i) 이 구문은 i번째 마을의 방문 여부를 판단한다.
1번과 3번마을을 방문했고 i가 2번째 마을일 때 101 % 010 비트마스킹으로
000이 되므로 2번 마을을 방문하지 않았음을 알 수 있다. N이 16이 최대이므로 완전탐색시 O(N!)라는 어마어마한 시간복잡도가 걸린다.
다이나믹 프로그래밍을 이용해 메모제이션을 사용해주어 시간복잡도를 줄여준다.
아직 완전
이해 한것이 아니다 비트마스킹은 쉽지만 역시 재귀로 빠지는 함수는 어렵다.
다시한번 공부 !!
외판원 순회 문제 (TSP: Travelling Salesman Problem)
TSP(Travelling Salesman Problem, 일명 ‘여행하는 외판원 문제’)는 조합 최적화(Combinatorial Optimization) 문제로 전산학에서 연구된 가장 유명한 문제 중 하나다.
여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다. 그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라"라고 표현할 수 있다. 이 문제는 반드시 시작점으로 돌아와야 한다는 제약 조건을 없애도 계산 복잡도는 변하지 않는다.
외판원 순회 알고리즘은 무식하게 풀 수 있다. 무조건 0번 도시에서 출발한다고 가정해도 경로의 길이는 다르지 않다. 그러면 남은 도시들을 어떤 순서로 방문할지를 정하기만 하면 된다. 남은 n-1개의 도시를 나열하는 방법으로는 (n-1)!가지가 있다. 그래서 재귀 호출을 통해 쉽게 외판원 순회 알고리즘을 설계할 수 있다. 그러나 보통 n!의 풀이는 사용하지 않는다. 12!만 해도 479,001,600라는 엄청난 수를 지니기 때문이다.
외판원 순회 알고리즘을 더 빠르게 구할 수는 없을까?
모든 정점을 한 번씩 방문하는(출발 정점 제외) 최단 순환 경로를 탐색하는데 최적의 효율로 탐색하기 위해서 사용한다. 정점 N의 최대크기는 16라고 해보자. 위에서 말했다시피 만약 완전탐색으로 모든 경로를 조회하면서 답을 구하려고 한다면 첫 번째 지점을 제외하고 탐색하여도 (16-1)! = 약 1.3조 정도가 되어 시간초과가 발생할 것이다. 게다가 모든 경로의 상태를 저장하는 n개의 상태를 저장하는 배열 크기도 필요하다.
DP 메모제이션
(16-1)!의 모든 경로를 조사하지 않고 중복된 경로를 제거하는 dp 메모제이션기법을 사용하면 된다. 동일한 하위 문제의 반복을 막아줌으로써 더 높은 효율로 연산이 이루어지게 해준다. 중복되는 경로의 조사를 제거해주는 것이다.
- 예를 들면, 피보나치 함수는 dp메모제이션 기법을 통해 O(2^n)의 복잡도를 O(n)까지도 줄여준다. 그렇다고 무조건 dp 메모제이션을 적용하면 O(n)으로 줄어든다는 뜻은 아니다. 각 문제 성질마다 다르다.
비트마스킹
비트마스킹을 사용하면 bit연산이기 때문에 다른 자료구조(boolean배열)을 사용하는 것보다 훨씬 빠르게 동작되고 코드도 간결해진다. 그리고 가장 큰 장점은 N이 16개인 경우 2^16가지의 경우를 16bit로 표현이 가능하다. (ex. 16개의 지점 중 1,3,4,5번 지점 방문 -> 0000 0000 0001 1101)
→ 정리하면 TSP(외판원 순회)는 최단 순환 경로를 탐색해야하는데 1) N! 의 중복 경로를 제거해주는 DP 메모제이션 기법을 사용한다. 그래도 2^N의 모든 경우의 수를 표현해야 하기 때문에 그만큼의 공간복잡도가 필요하다. 2) 메모리 사용량도 줄이고 성능 향상을 위해서 2^N의 경우의 수를 Nbit로 표현할 수 있는 비트마스킹으로 사용한다.
→ 최적화 접근 방식으로 DP 메모이제이션과 비트마스킹을 사용하여 해당 설명은 올라가야 할 계단의 수를 100 → 1로 줄여주는 설계 방법이라고 보면 된다.
왜 한 정점만 탐색해도 될까?
DP 메모제이션 기법으로 엄청나게 시간을 단축 할 수 있는 것은 그만큼 중복되는 경로가 많기 때문이다. TSP는 한 정점에서 다른 모든 정점을 순회하여 다시 출발 정점으로 돌아오는 최적의 경로를 찾는 알고리즘이다. 이 순회 경로는 싸이클로 n개의 정점 중 어느 정점에서 탐색을 시작을 해도 결과는 똑같다는 것을 알아야한다.
어차피 최적 경로 싸이클은 어디서 시작해도 다 똑같이 나온다. 그래서 한 정점에서만 탐색해줘도 된다.
- 1번에서 출발 : 1 → 2 → 5 → 3 → 4 → 1
- 2번에서 출발 : 2 → 5 → 3 → 4 → 1 → 2
- 3번에서 출발 : 3 → 4 → 1 → 2 → 5 → 3
외판원 순회 문제 풀어보기
백준 2098번 외판원 순회 - 풀이 과정