외판원 문제

외판원 문제(外販員問題, 영어: traveling salesman problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.

외판원 문제의 해결책.

정의

여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다.

그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라"라고 표현할 수 있다. 이 문제는 반드시 시작점으로 돌아와야 한다는 제약 조건을 없애도 계산 복잡도는 변하지 않는다.

응용

이 문제는 택배 회사 이외에도 실용적으로 널리 적용될 수 있다. 대표적인 예로, 인쇄회로기판을 만드는 공정도 외판원 문제로 모델링할 수 있다. 드릴로 회로 기판에 구멍을 뚫는 기계가 있다면, '도시'는 구멍에 해당하고 '이동 비용'은 드릴의 위치를 이동시키는 데 필요한 시간이라고 생각할 수 있다. 현재는 이런 문제가 있을 때 다항식 시간 내에 풀 수 있는 알고리즘이 없으므로 담금질 기법이나 유전 알고리즘으로 근사 해를 구하는 것이 일반적이다.

복잡도

외판원 문제는 NP-난해라는 것이 증명되었다. 특히 외판원 문제를 결정 문제 "$x$ 값이 주어졌을 때 $x$보다 비용이 적게 드는 회로가 있는가"로 변환하면 NP-완전이 된다. 외판원 문제는 NP-완전 문제 중에서도 어려운 편으로, 일반적인 외판원 문제에 대한 다항 시간 근사 알고리즘은 P=NP가 아닌 한 존재하지 않는다는 것이 밝혀져 있다.

외부 링크

• TSPLIB