외판원 문제

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

외판원 문제(Traveling salesman problem)는 이산 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.

[편집] 정의

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

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

[편집] 응용

이 문제는 택배 회사이외에도 실용적으로 널리 적용될 수 있다. 대표적인 예로, 인쇄회로기판을 만드는 공정도 외판원 문제로 모델링할 수 있다. 드릴로 회로 기판에 구멍을 뚫는 기계가 있다면, '도시'는 구멍에 해당하고 '이동 비용'은 드릴의 위치를 이동시키는 데 필요한 시간이라고 생각할 수 있다.

[편집] 복잡도

이 문제는 NP-hard라는 것이 증명되었다. 특히 외판원 문제를 결정 문제 "x 값이 주어졌을 때 x보다 비용이 적게 드는 회로가 있는가"로 변환하면, 이것은 NP-완전이다.

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