Clean Code hochulshin.com

Algorithm - Travelling Salesman Problem(TSP)

2015-08-15

문제

Travelling Salesman Problem(이하 TSP)은 외판원이 자신이 위차한 도시에서 출발해서 다른 도시들을 각각 한번씩 방문하고 다시 자기 도시로 돌아오는 가장 짧은 일주 경로를 알아내는 문제이다. 일반적으로 이 문제는 음이 아닌 가중치가 있는 방향성 그래프를 대상으로 한다. 그래프 상에서 일주 여행 경로는 한 정점을 출발해 다른 모든 정점을 한번씩 거쳐서 다시 그 정점으로 돌아오는 경로이다.

다양한 알고리즘

TSP를 해결하기 위한 다양한 알고리즘이 있는데 brute-force로 하면 시간이 너무나 많이 걸리고, Dynamic Programming을 이용해도 정점의 수가 20개 정도 되면 수십초의 시간이 걸리게 된다. 그래서 정점의 수가 매우 많은 경우 휴리스틱 알고리즘이나 근사값을 찾아내는 알고리즘을 사용한다. 그 중 하나는 Mimimum Spanning Tree(MST, Kruskal 또는 Prim 알고리즘)를 구성한 후 MST를 이루는 간선을 따라 이동하고 이미 갔던 간선을 다시 돌아와야 하는 경우엔 그 간선을 건너뛰는 방법으로 진행하는 방법도 있다. 이 글에서는 그 중 Dynamic Programming 기법을 이용하는 방법을 살펴보자

아이디어

정의

V는 모든 정점의 집합이고 A는 V의 부분 집합이라고 하자. 예를 들어 다음과 같다 .

V: {v1, v2, …, vn}, A: {v3, v4}

D[Vi][A]는 A에 속한 각 정점을 정확히 한번씩만 거쳐서 vi에서 v1으로 가는 최단 경로의 길이라 하자. 예를 들어 아래 그림에서 D[v2][A={v3, v4}]는 v2에서 v1으로 갈 때 v3와 v4를 거쳐서 가는 것이며, 아래의 두가지 길이 중 짧은 길이의 값을 가진다.

D[v2][A={v3, v4}] = min(len(v2 -> v3 -> v4 -> v1), len(v2 -> v4 -> v3 -> v1))

travelling-salesman-problem

Flow

풀고자 하는 TSP문제는 D[v1][{v2, v3, v4}]를 찾는 것이다. 즉, v1 -> {v2, v3, v4} -> v1인 최단 경로를 찾는 것이다. 그것을 위해 가장 짧은 단위부터 계산을 해서 전체 경로로 확장한다.

  1. v2, v3, v4에서 출발해 아무 정점도 거치지 않고 v1으로 가능 경우의 거리
    • D[v2][0] = 1 (v2에서 v1의 간선 거리)
    • D[v3][0] = 무한대 (v3에서 v1까지 직접 가는 경로가 없음)
    • D[v4][0] = 6 (v4에서 v1의 간선 거리)
  2. 하나의 정점을 거쳐 가는 경우
    • D[v4][{v2}] = 3 + 1 (v4->v2의 간선 거리 + v2에서 v1까지의 최소 거리)
    • D[v2][{v3}] = 6 + 무한대 (v2->v3의 간선 거리 + v3에서 v1까지의 최소 거리)
    • D[v4][{v3}] = 무한대 + 무한대 (v4->v3의 간선 거리 + v3에서 v1까지의 최소 거리)
    • D[v2][{v4}] = 4 + 6 (v2->v4의 간선 거리 + v4에서 v1까지의 최소 거리)
    • D[v3][{v4}] = 8 + 6 (v3->v4의 간선 거리 + v4에서 v1까지의 최소 거리)
  3. 두개의 정점을 거쳐서 가는 경우
    • D[v4][{v2, v3}] = min(v4->v2의 간선거리 + v2에서 v3거쳐 v1갈때까지의 최소거리,v4->v3의 간선거리 + v3에서 v2거쳐 v1갈때까지의 최소거리)
    • D[v3][{v2, v4}] = min(v3->v2의 간선거리 + v2에서 v4거쳐 v1갈때까지의 최소거리,v3->v4의 간선거리 + v4에서 v2거쳐 v1갈때까지의 최소거리)
    • D[v2][{v3, v4}] = min(v2->v3의 간선거리 + v3에서 v4거쳐 v1갈때까지의 최소거리,v2->v4의 간선거리 + v4에서 v3거쳐 v1갈때까지의 최소거리)
  4. 세개의 정점을 거쳐서 가는 경우 : 최적 일주 여행 경로
    • D[v1][{v2, v3, v4}] = min(v1->v2의 간선거리 + v2에서 v3,v4 거쳐 v1갈때까지의 최소거리,v1->v3의 간선거리 + v3에서 v2, v4거쳐 v1갈때까지의 최소거리, v1->v4의 간선 거리 + v4에서 v2, v3 거쳐 v1갈때까지의 최소거리)

알고리즘

일반화 시키면 다음과 같다.

A는 공집합이 아니면, D[vi][A] = min(W[i][j]+D[vj][A-{vj}]. A가 공집합이면, D[vi][0] = W[i][1]

vi에서 출발해서 정점의 부분 집합 A를 거쳐서 v1으로 가는 최단 거리는 A의 정점들을 하나씩 선택해 vj라고 하면 vi-vj간 간선 길이와 vj부터 A의 나머지 정점들을 지나 v1까지의 최단 거리의 합을 구하고 A의 정점 vj 중 그 거리가 가장 짧은 거리를 구해서 D[vi][A]의 값으로 한다. 그리고, vi부터 다른 정점을 지나지 않고 v1까지 가는 경우엔 vi와 v1의 간선 거리가 D가 된다.

구현은 복잡하기 때문에 Pseudo 코드를 간략히 설명하는 것으로 마친다.

int W[][] //그래프의 간선 길이 
int D[][] //n, V-{v1} 

tsp(n){ //n: 정점의 수
	for(int i = 2; i<= n-2; i++){
		D[i][0] = W[i][1] //D[vi][0]를 W[i][1]로 초기화
	}
	for(int k = 1; k<= n-2; k++)
		for k개의 정점을 포함한 V-{v1}의 모든 subset에 대해
			for A에 속하지 않고 v1이 아닌 vi에 대해
				D[i][A] = min(W[i][j] + D[vj]][A-{vj}])
	D[1][V-{v1}] = min(W[1][j] + D[vj][A - {v1}])
	return D[1][v-{v1}]
}

Comments