외판원 순회(Traveling Salesman Problem)
TSP
어떤 한 도시에서 출발해 모든 도시들을 거친 후
출발했던 도시로 돌아올 수 있는 최소 비용이 요구되는 방법
이러한 도로가 존재한다고 가정해보자.
어떤 순서로 순회해야 최소 비용으로 모든 도시를 방문하고 돌아올 수 있을까?
완전 탐색으로 그 해를 구하는 방법이 가장 간단하다.
단순히 DFS를 통해 해를 구할 수 있다.
이 때, 모든 정점을 시작점으로 DFS를 구할 필요는 없다.
무작위로 하나의 시작점에서 DFS를 진행한다.
여기서 의문점이 생길 수 있다.
0 - 1 - 2 - 3 경로와 2 - 3 - 0 - 1 경로는 서로 다른 경로인데요?
하나의 시작점에서만 DFS를 진행하면 이러한 경우는 고려하지 않게 되는데?
둘의 경로를 구성하는 순서가 일치하는 것은 아니다.
하지만 두 경로를 이동하는데 요구되는 비용도 다를까?
최소 비용이 요구되는 유일한 경로가 있고,
그 경로가 위와 같다고 가정하자.
이 경로의 시작점에 따라 비용이 달라질까?
어디서 시작하든, 요구되는 비용은 15이다.
해당 그림의 정점들을 모두 잇는 간선을 무작위 시작점에서 그려보자.
시작점은 비용에 영향을 미치지 않는다.
위의 경우에는 0 - 1 - 2 - 3과 1 - 0 - 2 - 3을 같은 경로라고 볼 수 있지만,
이는 두 도시를 잇는 간선이 양방향이기 때문이다.
간선이 단방향이면 0에서 1, 1에서 0 도시로 가는 비용이 다를 수 있기 때문에 두 경로를 다르게 봐야 하지만,
그래도 DFS를 한 정점에서만 실행하면 된다는 것은 동일하다.
따라서 이러한 방법으로 해를 구하면
첫번째 예시를 기준으로 대략 의 연산을 실행하게 되고
시간복잡도는 이 소요된다.
일 경우, 이 조금만 큰 값으로 설정되어도 어마어마한 시간이 소요된다.
외판원 순회와 같은 문제는 이 최대 16이기 때문에
이러한 방법으로 풀어낼 수 없다.
최적화
으로 줄일 수 있다.
앞서 사용한 방법은 연산의 중복이 존재한다.
이미 계산해서 구한 값을 또 다시 계산해서 구하고 있다.
예시를 살짝 변경하였다.
어느 구간을 중복해서 계산하고 있는지 확인해보자.
아래는 도시 0에서 DFS를 실행해서 탐색한 결과 중 일부이다.
0 - 1 - 3 - 2 - 4 - 0
0 - 3 - 1 - 2 - 4 - 0
이 경로들은 2 - 4 - 0
이라는 중복된 경로를 갖고 있다.
2 - 4 - 0
경로를 이동하는 데 요구되는 비용은 14이다.
부분 경로에 대한 비용을 한 번 계산하고 어딘가에 따로 저장하면,
그 부분 경로를 굳이 탐색하지 않아도 쉽게 비용을 계산할 수 있게 된다.
DP를 이용하면 해결이 가능하다.
중복된 경로가 2 - 4 - 0이 아니라
2 - 3 - 4 - 5 - ... - 16이라고 생각하면
중복 계산 해결은 필수적이다.
그렇다면,
2 - 4 - 0 경로를 탐색하려면, 비용 14가 요구된다.
1 - 3 - 5 - 7 - 9 경로를 탐색하려면, 비용 X가 요구된다.
이러한 값을 어떻게 효율적으로 기록할 수 있을까?
비트마스크를 이용하면 해결이 가능하다.
도시가 0부터 4까지 5개가 있다고 하고,
2 - 4 - 0
경로를 방문했다고 하면 이를 와 같이 나타낼 수 있다.
방문한 경로의 자릿수를 1로 바꿔주는 것이다.
(0, 2, 4 자릿수를 1로 변경)
그러면 10101은 10진수로 21이고
14의 비용이 요구되므로
dp[21] = 14 라고 저장하면 될까?
dp[] = dp[21] = 14와 같이 저장하면 안된다.
dp[방문 기록] = 비용
이 아니라
dp[현재 정점][방문 기록] = 비용
과 같은 형태로 저장해야 한다.
1차원 배열의 dp를 사용한다고 해보자.
정점 1에서 시작하고, 1 - 2 - 3 - 1
경로를 탐색해보면 비용은 9이고,
dp[] = 10이 수행된다.
(2-3-1
경로의 비용이 저장됨)
그 다음으로 1 - 3 - 2 - 1
경로를 탐색할 때,
2 - 3 - 1
경로의 비용이 사용되어 버린다.
2와 3은 단방향 간선 2개로 이루어져 있기 때문에
1 - 2 - 3
과 1 - 3 - 2
의 비용은 다르다.
단방향 간선을 전혀 고려하지 않은 메모이제이션이다.
dp[현재 정점][방문 기록] = 비용
을 보면
구하려는 정답은dp[시작점으로 돌아가기 직전의 정점][모든 정점에 방문했다는 기록]
이라고 생각할 수도 있는데,
정답은dp[시작점][시작점에 방문했다는 기록]
에 있다.
0번째 정점에서 시작하고 정점이 총 4개라면 정답은dp[0][1]
에 있는 것이지,
dp[3][15]
에 있는 것이 아니다.
단순히방문했다는 기록
이 아니라,
dp 배열을
이만큼 방문했는데, 방문하지 않은 다른 정점들에 가려면 비용이 얼마나 필요해?
라는 의미를 갖고 있는 배열이라 생각하면 하단에 등장할 코드를 이해하기 수월할 것이다.
풀이 과정 및 코드
과정은 다음과 같다.
1. 한 시작점에서 dfs를 실행한다.
2. 다른 탐색 정점을 방문하지 않았고, 해당 정점으로 가는 길이 있으면 이동한다.
3. 정점을 다 방문했으면, 그 시점의 정점에서 시작 정점으로 돌아갈 수 있는지 확인한다.
편의상 0번째 정점에서 시작하도록 하고,
실행하려는 함수를 tsp(현재 정점, 방문 기록)
이라고 하자.
tsp(0, 1)
이 수행된다.
정점이 4개면 모든 정점을 방문했을 때의 방문 기록은 이고,
(1 << 4) - 1
와 같이 비트 연산자를 이용해 나타낼 수 있다.
해당 정점의 방문 여부를 확인하기 위해서는
방문 기록 & (1 << i)
의 값이 0인지를 체크하고,
방문하지 않았으면 방문 기록 | (1 << i)
와 같이 작성한다.
tsp 함수 코드는 다음과 같다.
static int tsp(int currentVertex, int visited) {
if(visited == (1 << n) - 1) {
if(w[currentVertex][0] != 0)
return w[currentVertex][0];
return MAX;
}
if(dp[currentVertex][visited] != MAX)
return dp[currentVertex][visited];
for (int i = 0; i < n; i++) {
if(w[currentVertex][i] != 0 && ((visited & (1 << i)) == 0)) {
dp[currentVertex][visited] = Math.min(dp[currentVertex][visited], tsp(i, visited | (1 << i)) + w[currentVertex][i]);
}
}
return dp[currentVertex][visited];
}
여기서
if(dp[currentVertex][visited] != MAX)
return dp[currentVertex][visited];
처럼 나타내기 위해서는 main 함수에서
for (int i = 0; i < n; i++)
Arrays.fill(dp[i], MAX);
와 같이 dp의 값을 큰 값으로 초기화해 주어야 한다.
아니면 굳이 처음에 main 함수에서 큰 값으로 초기화해 주지 않고
if(dp[currentVertex][visited] != 0)
return dp[currentVertex][visited];
dp[currentVertex][visited] = MAX;
처럼 나타내도 된다.
참고로 MAX = Integer.MAX_VALUE와 같이 값을 초기화하는 실수를 만들지 않아야 한다.
dfs를 수행하는 과정에서 오버플로우가 발생할 위험이 있다.
적당히 큰 값으로 대체하자.
전체 코드
import java.util.*;
import java.io.*;
public class Main {
static int n;
static int[][] w;
static int[][] dp;
static final int MAX = 12345678;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
w = new int[n][n];
dp = new int[n][1 << n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
w[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(tsp(0, 1));
}
static int tsp(int currentVertex, int visited) {
if(visited == (1 << n) - 1) {
if(w[currentVertex][0] != 0)
return dp[currentVertex][visited] = w[currentVertex][0];
return MAX;
}
if(dp[currentVertex][visited] != 0)
return dp[currentVertex][visited];
dp[currentVertex][visited] = MAX;
for (int i = 0; i < n; i++) {
if(w[currentVertex][i] != 0 && ((visited & (1 << i)) == 0)) {
dp[currentVertex][visited] = Math.min(dp[currentVertex][visited], tsp(i, visited | (1 << i)) + w[currentVertex][i]);
}
}
return dp[currentVertex][visited];
}
}
visited의 경우의 수가 , 정점의 개수가 개이고
tsp 함수가 번의 루프를 돌고 있으므로
임을 알 수 있다.
Author And Source
이 문제에 관하여(외판원 순회(Traveling Salesman Problem)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bty5596/외판원-순회Traveling-Salesman-Problem저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)