핵심 인사이트 (3줄 요약)

  1. 본질: TSP (Traveling Salesman Problem, 외판원 문제)는 모든 도시를 정확히 한 번씩 방문하고 출발지로 돌아오는 최단 경로를 구하는 NP-hard 최적화 문제다.
  2. 가치: 완전 탐색 O(n!), DP+비트마스크 O(2ⁿn²)으로 소규모를 처리하고, Christofides 1.5-근사, 메타휴리스틱(유전 알고리즘, 시뮬레이티드 어닐링)으로 대규모를 실용적으로 해결한다.
  3. 판단 포인트: n≤20이면 DP 비트마스크, n≤100이면 Christofides, n>100이면 메타휴리스틱 또는 LKH (Lin-Kernighan-Helsgott) 알고리즘을 선택한다.

Ⅰ. 개요 및 필요성

TSP는 완전 가중치 그래프에서 모든 정점을 한 번씩 방문하고 출발점으로 돌아오는 최소 비용 해밀턴 회로를 찾는 문제다.

특성내용
복잡도 (결정 문제)NP-완전
복잡도 (최적화)NP-hard
완전 탐색O((n-1)!/2) ≈ O(n!)
DP + 비트마스크O(2ⁿn²) 시간, O(2ⁿn) 공간
Christofides 근사O(n³), 최적의 1.5배 이내

TSP가 필요한 상황:

  • 물류 배송 경로 최적화 (택배, 항공 화물)
  • 반도체 회로 기판 드릴링 경로
  • 유전체 서열 분석 (게놈 어셈블리)
  • 관광 일정 최적화

📢 섹션 요약 비유: 외판원 문제는 도시들을 모두 방문하는 가장 짧은 여행 경로를 찾는 것이다. 도시가 20개만 돼도 완벽한 답을 구하는 데 우주 나이만큼 걸릴 수 있다.

Ⅱ. 아키텍처 및 핵심 원리

DP + 비트마스크 알고리즘

dp[mask][v]: 방문한 도시 집합이 mask이고 현재 v에 있을 때 최소 비용

초기화: dp[1<<s][s] = 0  (도시 s에서 출발)

전이: for mask in 0..(1<<n)-1:
       for u in 0..n-1:
         if mask & (1<<u):  // u를 방문했을 때
           for v in 0..n-1:
             if not (mask & (1<<v)) and adj[u][v]:
               dp[mask|(1<<v)][v] = min(dp[mask|(1<<v)][v], dp[mask][u] + w(u,v))

정답: min(dp[(1<<n)-1][v] + w(v, s)) for all v

ASCII 다이어그램 — DP 비트마스크 상태

┌──────────────────────────────────────────────────────────┐
│  n=4 도시: {0,1,2,3}, 시작점: 0                          │
│                                                          │
│  비트마스크 예시:                                         │
│  mask=0001 (2진수) = 도시{0} 방문                        │
│  mask=0101 (2진수) = 도시{0,2} 방문                      │
│  mask=1111 (2진수) = 모든 도시 방문                      │
│                                                          │
│  DP 테이블 (일부):                                        │
│  dp[0001][0] = 0              (도시0에서 시작)            │
│  dp[0011][1] = w(0,1)         (0→1)                      │
│  dp[0101][2] = w(0,2)         (0→2)                      │
│  dp[0111][2] = min(w(0,1)+w(1,2), w(0,2)+... )           │
│  ...                                                     │
│  dp[1111][*]: 모든 도시 방문 후 각 마지막 도시의 최소 비용│
│                                                          │
│  전체 상태 수: 2^n × n = 2^4 × 4 = 64                   │
└──────────────────────────────────────────────────────────┘

근사 및 휴리스틱 알고리즘

방법시간 복잡도보장 비율특징
가장 가까운 이웃 (NN)O(n²)보장 없음빠름, 단순
Christofides 알고리즘O(n³)1.5배 이내MST + 완전 매칭
LKH (Lin-Kernighan)—보장 없음현재 최고 휴리스틱
유전 알고리즘—보장 없음대규모 실용적
시뮬레이티드 어닐링—보장 없음지역 최적 탈출

📢 섹션 요약 비유: Christofides는 "최적보다 절대 50% 이상 나쁘지 않은 답"을 보장하는 알고리즘이다. 완벽하진 않지만 수학적으로 "이 이상 나쁠 수 없다"는 상한선을 제공한다.

Ⅲ. 비교 및 연결

규모별 TSP 해법 선택

n ≤ 12:  완전 탐색 (브루트포스), O(n!)
n ≤ 20:  DP + 비트마스크, O(2ⁿn²)
n ≤ 100: Christofides 1.5-근사, O(n³)
n ≤ 1만: LKH, 메타휴리스틱
n > 1만: 고급 메타휴리스틱, 분산 컴퓨팅

TSP와 관련 문제

문제관계설명
해밀턴 회로결정 버전경로 존재 여부 (NP-완전)
VRP (Vehicle Routing)일반화다중 차량 TSP
중국 우편 배달부오일러 버전간선 방문 (다항식)
2-opt, 3-opt지역 탐색TSP 해 개선 휴리스틱

대칭 vs 비대칭 TSP

대칭 TSP (STSP): d(i,j) = d(j,i) — 무방향 그래프
비대칭 TSP (ATSP): d(i,j) ≠ d(j,i) — 방향 그래프
  → ATSP가 더 일반적, Christofides는 STSP에만 1.5배 보장

📢 섹션 요약 비유: 비대칭 TSP는 "서울→부산은 KTX, 부산→서울은 버스"처럼 방향에 따라 비용이 다른 경우다. 이 경우 Christofides의 1.5배 보장이 성립하지 않는다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

시나리오 1: 택배 배송 경로 최적화 (쿠팡, CJ 대한통운)

  • 하루 배송지 n=30~50개
  • DP 비트마스크: n=30 → 2^30×30 ≈ 320억 (실시간 불가)
  • 실용: 메타휴리스틱(유전 알고리즘) + 2-opt 개선 → 1초 이내 근사해

시나리오 2: 반도체 기판 드릴링 (PCB 제조)

  • 수천 개 홀을 최소 이동 거리로 드릴링
  • LKH 알고리즘: 현실적 최적에 가까운 해 도출

시나리오 3: 관광 일정 자동 생성 (여행 앱)

  • 관광지 n=10~15개 방문 순서 최적화
  • DP 비트마스크 O(2¹⁵×15²) ≈ 7백만 → 실시간 처리 가능

기술사 판단 포인트

상황판단
n ≤ 20, 정확도 중요DP + 비트마스크 O(2ⁿn²)
n ≤ 100, 근사 보장Christofides (1.5배)
대규모 실용LKH, 유전 알고리즘
삼각 부등식 만족Christofides 1.5-근사 보장
실시간 요구2-opt, 3-opt 지역 탐색

📢 섹션 요약 비유: TSP는 알고리즘 설계의 축소판이다. "완벽한 해"를 포기하고 "충분히 좋은 해"를 빠르게 구하는 트레이드오프를 명확하게 보여준다.

Ⅴ. 기대효과 및 결론

TSP (Traveling Salesman Problem)는 NP-hard 최적화 문제로, 문제 크기에 따라 완전 탐색, DP+비트마스크, 근사 알고리즘, 메타휴리스틱을 선택하는 전략적 접근이 필요하다. Christofides 알고리즘은 1.5배 근사 보장으로 이론적 안전망을 제공하며, 실무에서는 LKH와 메타휴리스틱이 현재 최고 성능이다.

핵심 결론: TSP는 "완벽한 해"를 포기하고 "실용적인 좋은 해"를 추구하는 알고리즘 공학의 철학을 가장 잘 보여주는 문제다.

📢 섹션 요약 비유: 완벽한 TSP 해를 구하는 것은 모든 퍼즐 조각의 완벽한 위치를 동시에 찾는 것처럼 어렵다. 실제 물류 회사들은 "99% 효율"로도 충분하기 때문에 완벽 대신 실용을 선택한다.

📌 관련 개념 맵

개념관계설명
해밀턴 회로결정 버전TSP의 존재 문제
DP + 비트마스크정확 알고리즘O(2ⁿn²), n≤20
Christofides근사 알고리즘1.5배 이내 보장
LKH휴리스틱현재 최고 성능
메타휴리스틱대규모 해법유전 알고리즘, SA
MST (최소 신장 트리)Christofides 구성 요소2-근사의 기반

📈 관련 키워드 및 발전 흐름도

[완전 탐색 (Brute Force) — O(n!) 폭발]
    │
    ▼
[동적 프로그래밍 + 비트마스크 — O(2ⁿ·n²), n≤20]
    │
    ▼
[2-근사 알고리즘 (MST 기반) — 1.5배 이내 보장]
    │
    ▼
[Christofides 알고리즘 — 이론적 최강 근사]
    │
    ▼
[LKH / 메타휴리스틱 — 실용 최고 성능 (물류·항공)]

NP-난해 문제인 TSP는 완전 탐색의 폭발적 복잡도를 벗어나 근사 알고리즘과 메타휴리스틱으로 실용적 해를 추구하는 방향으로 알고리즘 공학이 진화해 온 흐름이다.

👶 어린이를 위한 3줄 비유 설명

  1. 🗺️ 외판원 문제는 여러 도시를 모두 한 번씩 방문하고 집에 돌아오는 가장 짧은 여행 코스를 찾는 것이다.
  2. 🤯 도시가 20개만 돼도 가능한 경로가 2,432,902,008,176,640,000개(약 24경)나 되어서 모두 확인하는 것은 불가능하다.
  3. ✈️ 그래서 택배 회사나 항공사는 "완벽하지 않아도 충분히 좋은" 경로를 빠르게 계산하는 스마트한 방법을 사용한다.