[Algorithm] TSP 세일즈맨 알고리즘

TSP 알고리즘

: Traveling Sales Person Problem 은 1 부터 n 까지 도시를 방문하고 다시 처음으로 돌아오는 경로중 가장 작은 비용을 선택하는 문제

1. 완전 탐색 =  O(N!)

 -> n 이 조금만 커도 안됨

2. DP

 이미 방문한 노드들의 경로는 다음 경로를 결정할때 영향을 주지 않는다. 다만 이전에 방문 했는지 여부는 영향을 끼친다. 

 그 이후 값중 최소가 되는 경로를 TSP ( here , visit )로 나타내자.

 (1 ) visit 를 어떻게 표현할것인가  -> 비트마스크 (방문했으면 1, 아니면 0) // 방문여부만 중요

      ex ) 2, 3, 7번 방문 = 1000110

 (2)  점화식?

      here 이후의 선택은 방문하지 않은  i 노드로 가는 경로를 w[ here ] [ i ] 라 하면 노드 i 를 방문하는 경우 최소비용은 

      TSP( i , visit + ( 1<< i  ) ) + w [ here ][ i ] 이다.

      

     TSP(here , visit ) 는 이런 i 들 중 최소 Min (   TSP( i , visit + ( 1<< i  ) ) + w [ here ][ i ] )  가 된다.

  (3) 종료점

모든 노드를 방문한 케이스 visit = ( 1 << n ) -1 인 경우 , 마지막 노드인 here 에서 첫 노드인 0으로 돌아가는 w를 반환한다.

int tsp (int here ,int visit) {
int & ret = dp[here][visit];
 
if (ret != -1) return ret;
if (visit == bigo-1) return ret = w[here][0];
ret = 16000001;
for (int i = 0; i < n; i++) {
if (!visited[i] && w[here][i]!=0 ) {
visited[i] = true;
ret = min(ret, tsp(i, visit + (1 <<i) ) + w[here][i]);
visited[i] = false;
}
}
return ret;
}

관련 문제 : 백준 2098