traveling salesman problem

외판원 순회 (TSP) 알고리즘 개념

외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종이다. 브루트 포스로 해결한가지 정말정말 무식한 방법이 있긴 하다. n개의 점들을 도는 순서를 순열을 통해 구해놓고, 그 경로를 따라 가면서 거리를 구하는 것이다. 하지만 알다시피, n개 점들의 순열의 경우의 수는 n!개이다... n이 20만 되어도 2,432,902,008,176,640,000가지, 한국말로 '243경' 개의 경우의 수를 따져 주어야 한다.동적 계획법으로 해결1~n번 도시가 있고, 이 중 몇 개의 도시를 거친 후에 지금 판매원이 i번 도시에 있다.그럼, 이 중에서 거쳐오지 않았던 도시들 중에서 다음 도시를 정해야 한다.우리는 다음 도시로 이동했다고 '가정' 하는 방식을 사용할 것이다.좀 더 이..