외판원 문제, 모든 도시를 한 번씩 방문하는 가장 짧은 경로는?

외판원 문제, 모든 도시를 한 번씩 방문하는 가장 짧은 경로는?

택배 기사님들이 하루에 수십, 수백 개의 집을 방문하여 물건을 배달하는 모습을 보며 "저 많은 집을 어떤 순서로 가는 게 가장 빠를까?"라고 궁금해하신 적이 있으십니까? 혹은 주말에 여러 관광지를 둘러보기 위해 여행 계획을 짜면서 "어디부터 가야 기름값을 아끼고 시간을 절약할 수 있을까?" 하고 고민해 본 경험이 있으실 것입니다. 우리는 본능적으로 덜 걷고, 덜 운전하고, 더 빨리 도착하는 효율적인 경로를 찾고 싶어 합니다.

이처럼 여러 장소를 한 번씩만 방문하고 다시 출발점으로 돌아오는 가장 짧은 경로를 찾는 문제를 수학과 컴퓨터 과학에서는 '외판원 문제(Traveling Salesman Problem, TSP)'라고 부릅니다. 얼핏 보면 지도를 펴놓고 쓱 긋기만 하면 답이 나올 것 같은 아주 쉬운 문제처럼 보입니다. 하지만 이 문제는 사실 수학자들과 컴퓨터 과학자들을 수십 년간 골머리 앓게 만든, 세상에서 가장 어렵고 까다로운 난제 중 하나입니다. 오늘은 이 외판원 문제가 도대체 왜 어려운지, 그리고 우리 실생활에서 어떻게 쓰이고 있는지 아주 쉬운 예시를 통해 알아보겠습니다.

단순해 보이지만 풀기 힘든 수학적 미스터리

1. 도시가 늘어날 때마다 폭발하는 경우의 수

왜 이 문제가 그토록 어려울까요? 그 이유는 방문해야 할 도시가 하나씩 늘어날 때마다 계산해야 할 경로의 수가 기하급수적으로 늘어나기 때문입니다. 예를 들어, 도시가 3곳뿐이라면 가능한 경로는 단 2가지뿐이라 금방 계산할 수 있습니다. 하지만 도시가 5개가 되면 24가지, 10개가 되면 약 36만 가지의 경로를 비교해야 합니다. 만약 도시가 30개라면? 슈퍼컴퓨터로도 우주가 멸망할 때까지 계산해도 답을 다 찾지 못할 만큼 엄청난 숫자가 나옵니다. 이것을 '조합 폭발'이라고 하는데, 겉보기엔 단순한 경로 찾기 같지만 실제로는 우주의 별 개수보다 더 많은 경우의 수와 싸워야 하는 문제입니다.

2. 정답이 아닌 '가장 좋은 답'을 찾는 타협

도시가 100개, 1000개가 넘어가면 완벽한 정답(최적해)을 찾는 것은 사실상 불가능에 가깝습니다. 그래서 과학자들은 완벽한 100점짜리 답을 찾는 것을 포기하고, 대신 95점이나 98점짜리 '꽤 괜찮은 답(근사해)'을 빠르게 찾는 방법으로 방향을 틀었습니다. 예를 들어 "가장 가까운 옆 도시부터 일단 가보자"라거나, "무작위로 경로를 여러 개 만들어보고 그중 제일 짧은 것을 고르자"와 같은 전략을 씁니다. 비록 그게 수학적으로 완벽하게 가장 짧은 길은 아닐지라도, 현실적으로 충분히 쓸모 있고 시간을 아껴주는 경로이기 때문입니다.

3. 컴퓨터도 힘겨워하는 난제 중의 난제

이 문제는 컴퓨터 과학에서 'NP-난해(NP-hard)'라는 등급으로 분류됩니다. 이름부터 어렵게 느껴지지만, 쉽게 말해 "답이 맞는지 확인하는 건 쉽지만, 정답을 찾아내는 건 엄청나게 어렵다"라는 뜻입니다. 누군가 "이 경로가 100km야"라고 하면 그게 진짜 100km인지는 금방 계산할 수 있습니다. 하지만 "이보다 더 짧은 경로는 절대 없어?"라고 물으면 그걸 증명하기 위해 모든 경우를 다 뒤져봐야 하므로 컴퓨터조차 혀를 내두르게 됩니다. 그래서 외판원 문제는 컴퓨터의 성능을 테스트하거나 새로운 인공지능 알고리즘을 개발할 때 단골손님으로 등장하는 대표적인 문제입니다.

우리 일상을 움직이는 숨은 알고리즘

1. 새벽 배송과 택배 시스템의 핵심

우리가 주문한 물건이 다음 날 새벽 문 앞에 도착할 수 있는 비결 중 하나가 바로 이 외판원 문제를 응용한 경로 최적화 기술입니다. 쿠팡이나 마켓컬리 같은 물류 회사는 매일 밤 수만 건의 주문을 처리합니다. 배송 기사 한 명이 담당해야 할 50가구의 위치를 지도에 찍고, 어떤 순서로 돌아야 기름값을 아끼고 약속된 시간 안에 배달을 마칠 수 있을지 컴퓨터가 계산해 줍니다. 만약 기사님이 감으로만 길을 찾는다면 배송 시간은 두 배로 늘어나고, 우리는 신선한 야채를 제때 받지 못할지도 모릅니다. 물류비 절감과 빠른 배송의 일등 공신이 바로 이 수학 문제입니다.

2. 반도체 칩 설계와 드릴링 공정

컴퓨터나 스마트폰 안에 들어가는 반도체 기판을 자세히 보면 수천, 수만 개의 아주 작은 구멍이 뚫려 있습니다. 이 구멍들은 기계 팔이 움직이며 하나씩 뚫어야 하는데, 이때 기계 팔이 움직이는 거리를 최소화해야 만드는 시간을 줄일 수 있습니다. 구멍 하나를 도시 하나라고 생각하면, 이는 완벽하게 외판원 문제와 똑같습니다. 기계 팔이 헛되이 움직이는 시간을 0.1초만 줄여도, 수백만 개의 칩을 만들 때는 엄청난 생산성 향상으로 이어집니다. 첨단 반도체 기술 뒤에도 묵묵히 최단 경로를 계산하는 수학적 원리가 숨어 있습니다.

3. 유전자 분석과 DNA 지도 작성

생명 공학 분야에서도 이 문제는 아주 중요하게 쓰입니다. 인간의 유전자 지도를 만들 때, DNA 조각들을 올바른 순서로 맞추는 과정이 필요합니다. 이때 각 조각 사이의 연관성을 거리라고 가정하고, 전체 조각을 가장 매끄럽게 연결하는 순서를 찾는 것이 외판원 문제와 비슷합니다. 흩어진 퍼즐 조각을 가장 효율적으로 맞추는 순서를 찾는 것과 같습니다. 이 기술 덕분에 우리는 유전병을 연구하고 새로운 치료제를 개발하는 속도를 획기적으로 높일 수 있었습니다. 전혀 관계없어 보이는 생물학에서도 수학은 길잡이 역할을 하고 있습니다.

현실에서 더 똑똑하게 길을 찾는 방법

1. 눈앞의 이익만 쫓지 않는 지혜

외판원 문제를 풀 때 가장 흔히 쓰는 쉬운 방법은 '가장 가까운 이웃 도시'부터 가는 것입니다. 이를 '탐욕 알고리즘(Greedy Algorithm)'이라고 합니다. 당장 눈앞의 사탕을 줍는 것처럼 욕심을 부린다는 뜻입니다. 하지만 이 방법은 종종 함정에 빠집니다. 당장은 가까운 곳으로 갔지만, 그 때문에 마지막에 엄청나게 먼 거리를 돌아와야 할 수도 있기 때문입니다. 인생도 마찬가지입니다. 당장 눈앞의 쉬운 이익만 쫓다가는 결국 먼 길을 돌아가게 될 수 있습니다. 때로는 조금 멀어 보여도 전체적인 그림을 보고 경로를 선택하는 것이 더 빠를 수 있다는 교훈을 줍니다.

2. 자연에서 배우는 개미의 지혜

수학자들은 이 어려운 문제를 풀기 위해 자연을 모방하기도 합니다. 바로 '개미 알고리즘'입니다. 개미들은 눈이 잘 보이지 않지만, 페로몬이라는 냄새 물질을 남겨 동료들에게 먹이가 있는 가장 짧은 길을 알려줍니다. 처음에는 무작위로 길을 가지만, 짧은 길을 다녀온 개미가 더 많은 냄새를 남기게 되고, 결국 모든 개미가 그 짧은 길로 다니게 됩니다. 컴퓨터 프로그램도 이 원리를 흉내 내어 수많은 가상의 개미를 풀고, 시행착오를 거쳐 최적의 경로를 찾아냅니다. 하찮아 보이는 개미의 집단 지성이 슈퍼컴퓨터도 힘들어하는 문제를 해결하는 열쇠가 된 셈입니다.

3. 완벽하지 않아도 괜찮은 유연함

앞서 말했듯 도시가 많아지면 완벽한 정답을 찾는 것은 불가능합니다. 하지만 우리는 100점짜리 답을 찾지 못했다고 해서 배달을 포기하거나 여행을 취소하지 않습니다. 98점짜리 경로라도 충분히 훌륭하기 때문입니다. 외판원 문제는 우리에게 '완벽주의의 함정'에 빠지지 말라고 조언합니다. 모든 조건을 완벽하게 충족하는 최상의 선택을 하려다 시간을 낭비하기보다는, 주어진 시간 내에 찾을 수 있는 '최선의 선택'을 하고 행동으로 옮기는 것이 훨씬 효율적입니다. 때로는 적당한 만족이 완벽함보다 더 나은 결과를 가져옵니다.

결론

외판원 문제는 단순히 '길 찾기'를 넘어, 한정된 자원과 시간 속에서 최고의 효율을 찾아내려는 인류의 노력을 보여줍니다. 택배 상자가 우리 집 앞에 놓이기까지, 반도체가 만들어지기까지, 그리고 유전자의 비밀을 밝히기까지 이 수학적 원리는 보이지 않는 곳에서 세상을 최적화하고 있습니다. 비록 완벽한 정답을 찾는 공식은 아직 발견되지 않았지만(어쩌면 영원히 없을 수도 있지만), '더 나은 경로'를 찾기 위한 끊임없는 시도들이 우리의 삶을 풍요롭게 만들고 있습니다. 오늘 퇴근길이나 여행길에서 내비게이션이 알려주는 길을 보며, 그 뒤에 숨어 있는 치열한 수학적 고민들을 한 번쯤 떠올려 보시는 건 어떨까요?