외판원 문제

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

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

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

응용[편집]

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

복잡도[편집]

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