외판원 문제 도시를 순회하는 최적의 경로는

당신은 물건을 파는 외판원이다. 전국 5개의 도시에 물건을 배달한 뒤, 다시 출발한 집으로 돌아와야 한다. 조건은 딱 하나다. 기름값을 아끼기 위해 '가장 짧은 거리(최단 경로)'로 도시들을 방문하되, 한 번 방문한 도시는 두 번 다시 들르면 안 된다. 자, 지도를 펼치고 선을 그어보자. 5개 도시 정도는 눈으로 쓱 훑어봐도 어디를 어떻게 돌아야 가장 빠른지 5분 만에 계산할 수 있다. 그렇다면 도시가 100개라면 어떨까? 21세기 최첨단 인공지능 슈퍼컴퓨터에 이 문제를 입력하고 엔터를 치면, 컴퓨터는 정답을 내놓지 못하고 영원히 로딩 화면만 띄운 채 멈춰버리고 만다. 초등학생도 이해할 수 있는 이 미치도록 단순한 질문이 컴퓨터 과학과 수학의 가장 악명 높은 난제인 '외판원 문제(TSP, Traveling Salesperson Problem)'다. 도대체 도시 몇 개 도는 것이 왜 슈퍼컴퓨터를 뻗게 만드는지, '조합 폭발'의 기괴한 공포 속으로 들어가 보자.

팩토리얼(!)의 공포, 조합 폭발

도시가 5개일 때 외판원이 짤 수 있는 경로의 경우의 수는 몇 개일까? 첫 번째 갈 수 있는 도시가 5곳, 그다음 4곳, 3, 2, 1곳이므로 5x4x3x2x1 = 120가지다. 컴퓨터는 1초도 안 되어서 120개의 길이를 다 재보고 가장 짧은 길을 알려준다. 하지만 도시가 10개로 늘어나면 경우의 수는 10!(팩토리얼) = 360만 개로 껑충 뛴다. 도시가 20개가 되면 20! = 약 243경(京) 개가 된다. 만약 택배 기사님이 서울의 배송지 60곳을 돌아야 한다면 경우의 수는 60!인데, 이 숫자는 무려 '우주에 존재하는 모든 원자의 개수'보다 많아진다. 도시가 하나씩 늘어날 때마다 계산해야 할 덩치가 우주 팽창 속도보다 미친 듯이 커지는 현상, 이것을 수학자들은 '조합 폭발(Combinatorial Explosion)'이라고 부른다. 컴퓨터가 1초에 1경 번을 계산해도 도시 100개의 최단 경로를 완벽하게 찾으려면 우주의 나이(138억 년)보다 수억 배 더 긴 시간이 필요하다.

완벽한 정답을 포기하다, 휴리스틱(Heuristic)

완벽한 최단 거리(100점짜리 정답)를 찾는 것이 수학적으로 불가능(NP-Hard)하다는 것을 깨달은 과학자들은 전략을 바꿨다. "100점짜리 정답을 찾느라 100억 년을 낭비할 바엔, 1초 만에 '90점짜리 쓸만한 꼼수 정답'을 찾자!" 이것이 바로 '휴리스틱(Heuristic)' 또는 '근사 알고리즘'이다. 가장 단순한 꼼수는 '탐욕 알고리즘(Greedy Algorithm)'이다. 전체 지도를 볼 필요 없이, 그냥 지금 서 있는 도시에서 '가장 가까운 도시'로 무조건 이동하는 것이다. 이 방법은 나중에 엉뚱한 오지로 빠져서 거리가 길어지는 함정에 빠지기 쉽지만, 계산 속도는 번개처럼 빠르다. 실생활에서는 이 탐욕 알고리즘을 뼈대로 삼아 요리조리 수정하는 방식이 가장 많이 쓰인다.

자연에서 훔친 아이디어, 유전 알고리즘과 개미 떼

최근에는 인공지능 학자들이 자연계의 생명체들로부터 꼼수를 훔쳐 오고 있다. '유전 알고리즘'은 일단 아무 경로(염색체)나 수천 개를 랜덤으로 만들어 낸다. 그리고 길이가 짧은 우월한 경로들만 살아남게 한 뒤, 그 경로들을 반반씩 섞어(교차) 자식을 낳게 하고 가끔 길을 엉뚱하게 비틀어버린다(돌연변이). 이 진화 과정을 컴퓨터 속에서 수만 세대 반복하면, 기가 막히게 짧은 최적의 경로가 마법처럼 탄생한다. '개미 군집 최적화(ACO)'는 더 신기하다. 개미들이 먹이를 찾을 때 바닥에 페로몬을 흘리는 원리를 모방했다. 컴퓨터 속 가상의 개미 수만 마리를 도시에 풀어놓고, 짧은 경로를 다녀온 개미의 길에 더 진한 가상의 페로몬 수치를 부여한다. 결국 모든 개미가 페로몬 냄새가 가장 진한 가장 짧은 길로 우르르 몰려들며 정답이 찾아진다.

외판원 문제가 세상을 움직인다

외판원 문제(TSP)는 단순히 택배 아저씨의 배달 길을 찾는 문제가 아니다. 반도체를 공장에서 조각할 때 레이저 빔이 수만 개의 구멍을 뚫는 최단 동선을 짜는 것, 유전자(DNA) 서열의 조각들을 원래대로 가장 빠르게 꿰맞추는 것, 아마존 물류 창고에서 로봇이 짐을 집어오는 경로 등 현대 산업의 수조 원짜리 비즈니스 효율성이 모두 이 '조합 폭발'의 늪을 얼마나 꼼수(근사치)로 잘 피해 가느냐에 달려 있다. ![어두운 미로를 통해 진화하는 빛나는 유전 알고리즘으로, AI가 생물학적 진화(교차 및 돌연변이)를 사용하여 대략적인 경로를 찾는 방법을 보여줌](https://image.pollinations.