외판원 문제 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:GLPK solution of a travelling salesman problem.svg|섬네일|외판원 문제의 해결책.]]
'''외판원 문제'''(外販員問題, {{llang|en|traveling salesman problem}}) 또는 순회 외판원 문제는 [[조합 최적화]] 문제의 일종이다. 줄여서 '''TSP'''라고도 쓴다. 이 문제는 [[NP-난해]]에 속하며, 흔히 [[계산 복잡도 이론]]에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.

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

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

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

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

== 같이 보기 ==
* [[쾨니히스베르크의 다리 문제]]
* [[그래프 순회]]

== 외부 링크 ==
{{위키공용분류}}
* [https://web.archive.org/web/20170325123309/http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ TSPLIB]

{{전거 통제}}
{{토막글|컴퓨터 과학}}

[[분류:그래프 이론의 계산 문제]]
[[분류:NP-완전 문제]]
[[분류:운용 과학]]
[[분류:해밀턴 경로]]
[[분류:그래프 알고리즘]]
[[분류:조합 최적화]]
[[분류:NP-난해 문제]]