💥 무차별 대입(Brute-Force)의 한계 (n-1)!/2 가지
도시가 n개일 때 가능한 경로는 (n-1)!/2가지. 정확한 최적해를 구하려면
이 전부를 검사해야 하는데(NP-hard), 도시 수가 조금만 늘어도 우주 나이보다 오래 걸립니다.
| 도시 수 | 경로 가짓수 | 1억개/초로 계산 시 |
|---|
| 5 | 12 | < 1μs |
| 10 | 181,440 | 2ms |
| 15 | 43,589,145,600 | 7.3분 |
| 20 | 6.1 × 10¹⁶ | 19.3년 |
| 30 | 4.4 × 10³⁰ | 1.4 × 10¹⁵ 년 (우주 나이의 10만 배) |
→ 그래서 실전에서는 완벽하지 않아도 빠르고 충분히 좋은 해를 찾는 휴리스틱을 씁니다.
🧭 두 가지 휴리스틱
① 최근접 이웃 (Nearest Neighbor)
현재 도시에서 아직 안 가본 가장 가까운 도시로 계속 이동. 탐욕적(greedy)이라 빠르지만(O(n²)),
마지막에 멀리 돌아와야 하는 "손잡이" 모양 경로가 생기기 쉬움.
② 2-opt 지역 탐색
경로에서 두 간선을 골라 뒤집었을 때(교차 해소) 더 짧아지면 교체. 더 이상 개선이 없을 때까지 반복 →
지역 최적해(local optimum)로 수렴.
# 2-opt swap 핵심 로직
for i in range(1, n-1):
for j in range(i+1, n):
# 간선(i-1,i)+(j,j+1) vs (i-1,j)+(i,j+1)
old = dist(t[i-1],t[i]) + dist(t[j],t[j+1])
new = dist(t[i-1],t[j]) + dist(t[i],t[j+1])
if new < old:
t[i:j+1] = reversed(t[i:j+1]) # 교차 해소