Travelling salesman problem - TSP

TSP :
N개 도시가 있고, 세일즈맨은 1번 도시에서 부터 시작해서 모든 도시를 한번씩만 거쳐서 다시 1번 도시로 돌아와야 한다. 각 도시를 이동할때의 비용이 있고-d(i,j)- 이때 최소 비용을 구하는 문제다.

naive :
기본적으로 N개의 도시를 차례대로 나열하는 Permutation 문제라고 볼 수 있다. 따라서 이때의 time complexity는 O(n!) 가 된다. N이 10정도만 되어도 문제 풀기 쉽지 않은 수준이다. (10! = 3628800)

DP :
C(i, S) : 1에서 시작해서 집합S에 있는 모든 도시를 한번씩만 거치고 i 도시로 들어오는 최소 비용
이라고 정의하면,
그러면 우리가 구하고자 하는 값은
C(1, S-{1}) 이 된다.

그 다음은 이렇게 된다.

C(i, {2..N}) =  min << C( j, {2..N} - {j}) + d(j, i) >> where 2<=j<=N, i!=j,  

C(1, {2..N})  이 우리가 원하는 최종답이 된다.

C(i, {}) = d(1,i) 단, i!=1
C(i, {2}) = C(2, {}) + d(2,i)
C(i, {3}) = C(3, {}) + d(3,i)
...
C(i, {2,3}) = min << C(2, {3}) + d(2,i)  or C(3, {2}) + d(3,i) >>
...
이런식으로 C(1, {2..N}) 을 구하게 된다.

그림으로..

집합S를 캐쉬로 표현할때는 bit 로 포함되고 안되고를 표현하면 되는데,
예를 들면, N=4 일때 {2,3,4} 를 표현하면 2^4-2 가 된다. 즉. 1110 (0은 1이 포함되지 않았다는 의미이다)

나중에 어떤 순서로 도시를 방문하는지 알고 싶으면 parent[S] 를 저장하고 있으면 된다.

나의 구현은 여기에

reference ::
https://github.com/evandrix/SPOJ/blob/master/DP_Main112/Solving-Traveling-Salesman-Problem-by-Dynamic-Programming-Approach-in-Java.pdf
https://www.youtube.com/watch?v=aQB_Y9D5pdw