결론부터 말하자면, TSP(외판원 문제)는 도시 수가 20개 정도까지는 동적 프로그래밍으로, 그 이상은 근사 알고리즘을 통해 현실적인 시간 내에 풀 수 있습니다. 완전 탐색 방식으로는 도시 15개만 되어도 계산 폭발로 인해 사실상 풀이가 불가능합니다.
TSP, 왜 이렇게 유명한가요? (NP-hard 문제의 핵심)
TSP(Traveling Salesman Problem, 외판원 문제)는 모든 도시를 정확히 한 번씩 방문하고 출발점으로 돌아오는 최단 경로를 찾는 문제입니다. 정의는 매우 단순하지만, 도시 수 n이 증가함에 따라 가능한 경로의 수는 (n-1)!/2로 기하급수적으로 늘어납니다. 예를 들어 도시 20개일 경우 경우의 수는 약 6 x 10¹⁶가지에 달하며, 이는 일반적인 컴퓨터로는 우주의 나이를 넘어서는 시간이 소요될 수 있습니다. 이러한 특성 때문에 TSP는 NP-hard 문제로 분류되며, 물류 경로 최적화, 반도체 회로 설계 등 다양한 실제 산업 문제 해결에 중요한 열쇠가 됩니다. 수십 년간 전 세계 연구자들이 TSP의 효율적인 해법을 찾기 위해 노력하고 있습니다.
도시 20개까지 가능한 완전 탐색과 동적 프로그래밍 (Held-Karp)
관련 글
가장 직관적인 TSP 해결 방법은 완전 탐색(Brute Force)입니다. 이는 가능한 모든 경로를 탐색하고 그중 최단 경로를 찾는 방식이며, 시간 복잡도는 O(n!)입니다. 도시 10개 정도까지는 비교적 빠르게 계산되지만, 15개를 넘어가면 응답이 없을 정도로 느려집니다. 단순히 느린 것이 아니라, 도시 수가 증가함에 따라 계산량이 폭발적으로 늘어나기 때문에 구조적으로 비효율적입니다.
수백 개 도시, 현실적인 해법은 근사 알고리즘
물류나 배달 경로처럼 도시 수가 수백 개 이상으로 많아지면, 최적해를 찾는 것은 현실적으로 불가능합니다. 이럴 때는 최적해는 아니더라도 '충분히 좋은 해'를 빠르게 찾는 근사 알고리즘(Approximation Algorithm)을 사용합니다. 가장 대표적인 근사 알고리즘 중 하나는 Nearest Neighbor Heuristic(NN)입니다. 현재 위치에서 가장 가까운 아직 방문하지 않은 도시로 계속 이동하는 방식입니다. NN 알고리즘의 시간 복잡도는 O(n²)으로 매우 빠르지만, 최적해보다 평균 20~25% 정도 더 긴 경로를 생성할 수 있습니다.
TSP 코딩 경험으로 얻은 알고리즘 복잡도 이해
8년간 알고리즘 강의를 진행하면서 '경우의 수 폭발'이라는 개념을 이론적으로만 설명해왔습니다. 하지만 TSP 문제를 직접 파이썬 코드로 구현하고 실행해보니, 이 말이 단순한 수사가 아니라 실제 계산 과정에서의 물리적인 한계라는 것을 피부로 느낄 수 있었습니다. 이론과 실제 구현 사이의 간극이 이렇게 클 수 있다는 것을 깨달으며 오히려 제가 더 많이 배운 경험이었습니다. TSP는 완전 탐색, 동적 프로그래밍, 근사 알고리즘의 차이를 가장 명확하게 보여주는 훌륭한 예시입니다. AI 프로그래밍이나 알고리즘 최적화를 공부하는 분이라면, TSP를 직접 코드로 구현해보는 경험은 이론적 지식을 실제 문제 해결 능력으로 전환하는 데 큰 도움이 될 것입니다. 강의실 슬라이드에서만 보던 NP-hard 문제가 코드 한 줄을 통해 이렇게 생생하게 다가올 줄은 몰랐습니다.
TSP 알고리즘의 모든 것을 직접 코드로 확인해보세요.
