외판원 문제

위키백과 ― 우리 모두의 백과사전.

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

[편집] 정의

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

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

[편집] 응용

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

[편집] 복잡도

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

이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.