올여름 유럽 여행을 계획 중인 A 씨는 프랑스, 스페인, 이탈리아 3개국의 8개 도시를 방문하고 싶어 한다. 그는 최소한의 비용과 시간으로 이들 도시를 한 번씩 들른 뒤 다시 부산으로 돌아오는 여행을 꿈꾸고 있다. 과연 어떤 경로가 가장 효율적일까? 외국 여행을 계획했던 사람이라면 한 번쯤 고민해봤을 법한 이 문제는 수학에서는 흔히 ‘외판원 문제’로 불린다. 일반인에게는 다소 낯설 수 있지만, 조합 최적화 분야에서는 매우 잘 알려진 대표적 문제 중 하나다. 간단히 말해, 주어진 여러 도시를 모두 한 번씩 방문하고 출발지로 되돌아오는 가장 짧은 경로를 찾는 것이 핵심이다. 소위 점과 점을 잇는 ‘한 붓 그리기’와 유사하다고나 할까.

겉보기에는 간단해 보이지만 방문 장소가 늘어날수록 가능한 경로의 수는 기하급수적으로 늘어 최적경로를 찾는 것은 매우 복잡해진다. 예를 들어 여행지 4곳만 있는 때는 3가지 경로가 가능하지만, 8곳이라면 2520개의 경로가 생성된다. 수천, 수만 개의 여행지를 고려해야 한다면 대형 컴퓨터를 동원해 풀어야 할 정도로 복잡해진다. 이런 이유로 사실상 정답을 찾기보다는 근삿값으로 가장 가까운 경로를 찾는 것이 현실적인 목표가 된다. 이 문제는 18세기 ‘수학계의 모차르트’라 불린 레온하르트 오일러가 1759년에 처음 제안한 것으로 알려져 있다.

외판원 문제는 컴퓨터 과학, 수학, 운영 연구 등 다양한 분야에서 기본적으로 다뤄지고 있으며, 최근에는 실생활과 산업 전반에 걸쳐 널리 적용되고 있다. 특히 택배 물품을 전달할 최적의 경로를 찾거나, 컴퓨터 기판에 구멍을 뚫을 때 드릴이 움직여야 할 가장 효율적인 경로를 결정하는 데도 활용된다. 실제 미국 아마존에서는 택배 배송 트럭의 경로 최적화에 외판원 문제를 적용해 동선을 효율적으로 조정하고 있다.

세계적인 수학자 윌리엄 쿡 교수는 최근 한국 경찰청의 술집 위치 데이터를 바탕으로 전국 8만 1998개 술집을 모두 걸어서 방문하는 최단경로를 계산해 화제가 됐다. 3개월간 여러 대의 컴퓨터를 병렬로 돌려 얻은 결과, 최단경로에 드는 시간은 178일 1시간 56분 17초였다. 이제 외판원 문제는 택배 차량 운전자, 여행 일정을 짜는 이, 외근 나가는 직장인까지, 우리의 생활 속에 너무나 자주 등장한다. 외판원 문제를 통해 복잡다단한 세상 속에서 어떤 방식이 진정 효율과 질서를 찾아가는 최적의 방식인지를 우리 모두 배웠으면 한다.

정달식 논설위원 dosol@busan.com