[알고리즘] 외판원 순회 문제 (TSP: Traveling Salesman Problem)

외판원 순회 문제 (TSP: Traveling Salesman Problem)

1부터 N번까지의 도시들이 있고 각 도시들 사이에는 길이 있으며 비용이 존재한다.(길이 없는 경우도 존재)

한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한번 갔던 도시로는 다시 갈 수 없다. 이 때 여행 비용이 최소가 되는 경로를 구하라.

---

모든 경우에 대해 계산 할 경우  O(n!)의 시간 복잡도를 가지기 때문에 DP로 푼다.

 

시작 지점은 어떻게 정할까?

→ 상관없음. 어느 점에서 시작하든지 동일한 결과가 나옴.

1,2,3,4번 도시가 다음과 같고 빨간 색으로 표시된 경로가 최소 비용이 드는 순회 경로라고 하자.

이때 경로는 

1-4-2-3-1

2-3-1-3-2

3-1-4-2-3

4-2-3-1-4

로 나타낼 수 있다.

즉 순환하는 경로이기 때문에 시작점을 어디로 정해도 상관이 없기 때문에 임의의 도시를 출발지로 선택하면 된다.

 

중복되는 경로 줄이기

다음 그림과 같은 경로가 존재한다고 해보자.

 

이때 1-2-3-4-5-1 의 경로와 1-3-2-4-5-1의 경로의 비용을 계산해 본다고 하자.

1-2-3-4 / 1-3-2-4의 비용은 다르기 때문에 각각 계산해야 하지만 4-5-1의 비용은 두 경로 모두 동일하기 때문에 한번만 계산하도록 하면 시간 복잡도를 줄일 수 있다.

 

즉, cost[현재 도시의 index][이때까지 방문한 도시]배열에 처음가는 경로의 비용을 저장해두고, 다시 방문할 때는 저장된 값을 사용하는 메모이제이션 (Memoization) 방식을 사용한다.

 

방문한 도시 목록을 저장하는 방법

위의 예시에서 현재 도시의 index는 4로 표시하면 된다. 그렇다면 이때까지 방문한 도시 목록을 어떤 방식으로 표현할 수 있을까? 

비트 마스크(Bitmask)를 사용한다. 1~5번의 도시가 있을 경우,

00000 → 방문x

10000 → 5번 도시만 방문

10101 → 5,3,1번 도시 방문

11111 → 모든 도시 방문

과 같은 방식으로 나타낼 수 있다.

 

풀이코드(C++)

백준2098번: 외판원 순회

2098번: 외판원 순회

#include <iostream>
#include <string>
#include <memory.h>

#define maxVal 100000

using namespace std;

int N, done=0;
int move_cost[16][16];
int cost[16][maxVal];

int travel(int idx, int visited) {
	if (cost[idx][visited] != 0) return cost[idx][visited];
	if (visited == done) {
		if (move_cost[idx][0] == 0) cost[idx][visited] = -1;
		else cost[idx][visited] = move_cost[idx][0];
	
		return cost[idx][visited];
	}

	int minCost = 0;
	int sum = 0;
	int v;

	for (int i = 1; i < N; i++) {
		if (visited & (1 << i)) continue;
		if (move_cost[idx][i] == 0) continue;

		v = visited + (1 << i);
		if (travel(i, v) < 0) continue;

		sum = move_cost[idx][i] + travel(i,v);
		if (minCost == 0 || minCost > sum) minCost = sum;
	}

	if (minCost == 0) cost[idx][visited] = -1;
	else cost[idx][visited] = minCost;

	return cost[idx][visited];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	memset(cost, 0, sizeof(cost));

	cin >> N;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> move_cost[i][j];
		}
		done = done << 1;
		done++;
	}
	done -= 1;
	
	cout << travel(0,0) << endl;

	return 0;
}