외판원 문제(TSP)와 휴리스틱: 최적해가 불가능한 문제를 푸는 근사 알고리즘 전략

핵심 메시지

• 외판원 문제(TSP)는 모든 도시를 정확히 한 번씩 들르고 출발지로 돌아오는 최단 경로를 찾는 문제로, NP-난해에 속해 최적해를 빠르게 구할 수 없다.
• 완전탐색은 도시 수가 20개만 돼도 (n-1)!/2 경로 때문에 사실상 불가능하다.
• 현실에서는 최적해 대신 '충분히 좋은' 근사해를 빠르게 찾는 휴리스틱·근사 알고리즘을 쓴다.
• 탐색(exploration)과 활용(exploitation)의 균형이 좋은 해를 찾는 핵심 원리이며, 이는 컴퓨터과학 여러 분야에 공통으로 나타난다.

쉽게 이해하기

TSP는 모든 주요 도시를 한 번씩 방문하고 출발지로 돌아오는 최단 경로를 찾는 문제다. 도시를 정점, 경로를 간선으로 보는 그래프 문제로 모델링하며, 보통 두 도시 간 거리가 양방향 동일한 대칭 TSP와 직선 경로가 가장 짧다는 삼각 부등식을 가정한다. 단순해 보이지만 컴퓨터과학에서 가장 어려운 문제 중 하나다.

가장 직접적인 방법인 완전탐색은 가능한 모든 경로를 따져 최단을 고른다. 그러나 출발점을 고정하고 방향 중복을 제거해도 경로 수는 (n-1)!/2로 폭발해, 도시 20개만 돼도 계산이 비현실적이다. 동적 계획법으로 다소 키울 수 있지만 본질적으로 지수 시간이며, TSP가 NP-난해라 다항 시간 알고리즘은 없을 것으로 본다.

그래서 관점을 '최적해'에서 '충분히 좋은 해'로 바꾼다. 가장 자연스러운 최근접 이웃 휴리스틱은 매 단계 가장 가까운 미방문 도시를 택한다. 해의 품질은 최적해를 모를 때 비교할 수 없으므로, 대신 최소 신장 트리(MST)에서 유도한 '원-트리 하한'과 비교한다. 무작위 유클리드 거리에서 최근접 이웃은 이 하한의 약 1.25배 수준으로, 단순함에 비해 꽤 좋다. 모든 간선을 한꺼번에 보는 그리디 휴리스틱은 평균적으로 조금 더 낫다.

MST를 적극 활용한 것이 크리스토피데스 알고리즘이다. 투어는 모든 정점의 차수가 2여야 하므로, MST의 홀수 차수 정점들을 최소 가중치 완전 매칭으로 짝지어 모든 차수를 짝수로 만든다. 이어 모든 간선을 한 번씩 지나는 오일러 투어를 만든 뒤, 이미 방문한 정점을 건너뛰어 유효한 TSP 투어로 변환한다. 무작위 사례에서 하한의 약 10% 이내, 최악의 경우에도 최적해의 1.5배 이내가 수학적으로 증명됐고, 1976년 발견 이후 50년간 이 한계는 거의 개선되지 않았다.

초기 해를 얻은 뒤에는 국소 탐색으로 개선한다. 무작위 교환, 그리고 두 간선을 다른 방식으로 잇는 2-opt, 세 간선을 바꾸는 3-opt 같은 k-opt 기법이 대표적이다. 다만 국소 탐색만으로는 국소 최소에 갇힐 수 있다. 시뮬레이티드 어닐링은 일부러 더 나쁜 해도 확률적으로 받아들여 국소 최소를 탈출하며, 이 확률은 '온도'에 따라 정해져 초반엔 탐색을, 후반엔 수렴을 유도한다(이름은 결정화 물리에서 따왔다). 개미 군집 최적화는 여러 '개미'가 거리와 페로몬(보상) 행렬을 함께 보고 경로를 확률적으로 고르며, 좋은 경로일수록 큰 보상을 쌓아 점점 더 나은 해로 수렴한다.

주요 인사이트

• TSP를 푸는 강력한 전략 하나는 더 쉬운 문제(최소 신장 트리)를 풀어 어려운 문제의 좋은 해로 끌어올리는 것이며, 이는 문제 해결에서 반복적으로 등장하는 주제다.
• 시뮬레이티드 어닐링의 교훈은 '더 나아지기 전에 일부러 나빠지는 것을 허용'해야 국소 최소를 벗어나 전역 최적에 가까워질 수 있다는 점이다.
• 최적해를 검증조차 할 수 없을 때는 절대 기준 대신 MST 기반 하한 같은 '하한값'과 비교해 근사해의 품질을 가늠한다.
• 탐색과 활용의 균형이라는 개념은 TSP뿐 아니라 강화학습 등 컴퓨터과학 여러 분야를 관통하는 핵심 원리다.

자주 묻는 질문

관련 AI 소식