언어: 자바
난이도는 TSP1, TSP2는 중, TSP3는 상이다. TSP3는 풀지 못하였다.
외판원 문제(Traveling Salesman Problem) 은 NP-Hard로 유명한 알고리즘 문제이다. Wiki에도 정의 되어 있는데, 여러 푸는 방법이 기술되어 있어 참고할 만 한다.
WiKi Link: Traveling Salesman Problem
정확한 해를 구하기 위해서는 모든 조합을 계산해 보는 brute force search 의 경우 실행 시간이 O(n!) 가 되어 실질적으로 사용이 불가능하게 된다. 개선된 버전은 Dynamic Programming 기법을 이용하는 것인데 이때 실행 시간은 O(n^2*2^n) 이 된다.
이번 포스팅에서는 dynamig programming 방법에 대해서 기술해 본다. Dynamic programming 은 해 내에 sub해가 존재하는 경우에 사용한다.
예를 들어 도시 {0,1,2,3,4} 가 있고 0 에서 출발해서 {1,2,3,4}를 방문하는 최소 경로를 MinPath(0,{1,2,3,4}) 라고 한다면 {0,1,2,3,4}의 최소 경로는
min(
MinPath(0,{1,2,3,4}),
MinPath(1,{0,2,3,4}),
MinPath(2,{0,1,3,4}),
MinPath(3,{10,,2,4}),
MinPath(4,{0,1,2,3})
)
이 된다. D(x,y) 를 x와 y의 거리라고 한다면 MinPath(0,{1,2,3,4}) 는 다음과 같이 된다.
MinPath(0,{1,2,3,4}) = min(
D(0,1) + MinPath(1,{2,3,4}),
D(0,2) + MinPath(2,{1,3,4}),
D(0,3) + MinPath(3,{1,2,4}),
D(0,4) + MinPath(4,{1,2,3}),
)
이렇게 Sub 경로의 MinPath를 구해나가다 보면 결국 MinPath(0,{1}), MinPath(0,{2}) .. 와 같이 경유하는 노드(=도시) 없이 해당 노드로만 이동하게 되는 값 까지 이르게 되어 전체 해의 계산이 가능해진다.
실제로 구현하는데 있어서 방문하고자 하는 노드들을 표현하는 것이 어렵다. 검색을 해보면 bit 로 표현한 경우가 많은데, 본 포스팅에서도 bit로 표현한다.
예를 들어 {0,1,2,3,4} 는 bit로 11111 로, {1,2,3,4}는 11110으로, {1,3,4}는 11010 으로 표현하는 것이다. 각 도시간의 거리는 매트릭스로 표현된다. 즉 matrix[i][j] 는 i 에서 j로 가기 위한 거리를 나타낸다.
다음은 이를 자바로 구현한 코드이다. 알고스팟의 TSP1과 TSP2는 통과하는데, TSP3는 런타임 오류가 난다. 아마 Cache 저장을 위해서 double 값의 Array를 할당하면서 메모리 오류가 발생했을 가능성이 높다. TSP3는 이를 해결하는 것이 필요할듯 하다.
