TSP란 Traveling Salesman Problem으로 외판원 문제로 많이 알려져있다.
wiki백과를 찾아보면
외판원 문제(Traveling salesperson problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.
라고 어렵게 적혀있다ㅡ_ㅡ;
간단히 적어보면 그래프로 설명하면 되는데 아래와 같은 그래프가 있을때 각각의 정점을 있는 간선에는 가중치가 주어져 있다. 이 그래프에서 정점 v1에서 모든 정점을 거쳐 v1으로 다시 돌아 오기까지거치 간선들의 가중치가 최소가 되도록 하는 경로를 구하는 문제다. 이렇게 적고보니 별거 아닌거 같기도ㅋ
