수학사랑

n 개의 도시를 방문해야 하는 영업사원이 있다.

n개의 도시를 적어도 한번 최소한의 거리를 이동해서 모두 방문하기 위해서는 어떻게 해야 할까?

이 문제가 바로 영업사원 방문 문제이다.

영업사원 방문 문제는 travelling salesman problem을 번역한 것으로 한자로는 營業社員 訪問 問題라고 쓴다.

travelling salesman problem → 營業社員 訪問 問題 → 영업사원 방문 문제

travelling salesman problem을 글자 그대로 번역하면 '여행하는 영업사원 문제'인데 번역하면서 '영업사원 방문 문제'가 된 것이다.

이 문제는 주어진 n 개의 도시를 꼭지점으로, 그리고 두 도시를 연결하는 도로를 변으로 하는 그래프에서 해밀톤 회로를 찾는 문제이다.

그러나 아직까지 이 문제를 해결하는 일반적인 알고리즘은 알려져 있지 않다.