알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드)

 < TSP(The Travling Salesperson Problem) >

 

외판원이 출장시간을 줄이기 위해 거주하고 있는 도시에서 출발하여

 

각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아온다고 했을 때

 

가장 짧은 여행길을 찾는 알고리즘

 

start node가 있고 n-1 개의 node를 거쳐 1번 node로 돌아간다. 

 

brute-force 알고리즘을 이용해서 문제를 해결할 수도 있지만

 

 

Brute-Force를 이용했을 때 시간복잡도

 

 

n이 20만 되어도 걸리는 시간복잡도는 19!usecs(대략 3857년)으로 

평생 구하지 못한다.

 

하지만 동적프로그래밍을 이용한 TSP알고리즘이면 45초만에 해결가능하다.

  

 

 

 

그렇다면 예제를 TSP알고리즘을 이용하여 풀어보자

 

다음과 같이 가중치가 있고, 노드 4개로 이루어진 그래프(V)가 있다. 

그래프 V  

 

그리고 위 그래프를 인접매트리스 W로 나타내면 다음과 같다. 

 

Adjacent matrix W

 

 

그리고 다음과 같이 정하고 들어가자 

 

- A = V의 부분집합

(공집합도 포함하며, v1은 포함하지 않는다)

 

ex) 

A = {}

A = {v2}

A = {v2, v3}

 

 

- D[vi][A] = vi노드에서 시작해서 A의 모든 노드를 거친 후,  마지막 v1을 들렀을 때

거리의 최솟값

 

ex) 

A = {v3, v4}일 때 

D[v2][A] = min(length(v2, v3, v4, v1), length(v2, v4, v3, v1))

 

 

 

 

이를 일반화하면 다음과 같다.

 

 

그리고 우리가 원하는 값은 v1에서 출발하여 모든 노드를 거쳐 다시 v1으로 돌아오는 최소 값이므로

 

 

D는 다음과 같이 채워진다.

 

행의 크기는 n-1,열의 크기는 nC0 + nC1 + ... + nCn-2

 

 

 

 

 

<TSP c++ 의사코드>

void travel(int n , const number W[][], index P[][], number& minlength){

index i, j, k;
number D[1 .. n][subset of V - {v1}];

for(i = 2; i <= n; i++)  // 원소의 개수가 0일때 공집합처리 
D[i][∅] = W[i][1];

for(k = 1; k <= n-2; k++) // 원소의개수가 1 ~ n-2까지 
for(V-{v1}의 원소의 갯수가 k인 부분집합 A) // n-1Ck
for(i != 1이고 vi가 A에 속하지 않을 때 모든 i값){ // n-1-k (k는 이미지나간 노드)
D[i][A] = min(W[i][j] + D[j][A - {vj}]);(j는 A에 속하는 노드 번호) // k (A집합원소수 만큼)
P[i][A] = 최소가 되는 j값;
}


// n-2의 크기까지 거쳤으므로 아직 거치지 못한 노드가 하나 남았다.
// 마지막으로 거쳐준다. 
D[1][V - {v1}] = min(W[1][j] + D[j][V - {v1, vj}]);(j는 A에 속하는 노드 번호)
P[1][V - {v1}] = 최소가 되는 j 값;
minlength = D[1][V - {v1}]l


}

 

 

 

 

 

< TSP의 시간복잡도 >

 

 

 

 

 

 

 

< TSP의 공간복잡도 > 

 

 

출처 : Foundations of Algorithms, Using C++ Pseudocode