외판원 문제

1 개요

travelling salesman problem, traveling salesperson problem (TSP)

외판원 문제, 순회 외판원 문제, 순회 세일즈맨 문제

• "가중치 완전 그래프에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라"
• "여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서는 무엇인가?"
• 조합 최적화 문제의 하나
• NP-난해에 속한다.
• 응용예시: 택배회사, 인쇄회로기판 공정(드릴 이동 비용)

 

2 같이 보기

• 해밀턴 순환
• NP-난해

3 참고

• 영어 위키백과 "Travelling salesman problem"