외판원 문제(TSP)와 그 친척들은 NP-난해다 — 정답을 다항시간에 구하는 길은 알려져 있지 않다. 최근접 이웃(nearest neighbor)은 그 벽 앞에서 가장 먼저 손이 가는 휴리스틱이다. 매번 현재 위치에서 가장 가까운 미방문 노드를 골라 잇는다. 한 줄의 욕심으로 그럴듯한 경로가 나온다 — 그러나 마지막에 외딴 노드 하나가 남으면 긴 점프가 강요된다. 이 페이지는 NN의 근사비를 증명하고, 그 약점을 swap·2-opt 국소탐색이 어떻게 보강하는지 추적한다.
n개의 지점과 그 사이의 거리 d(i, j)가 주어진다. 한 지점에서 출발해 모든 지점을 정확히 한 번씩 방문하고 돌아오는 — 또는 전부 방문하기만 하는 — 가장 짧은 경로를 구한다. 이것이 외판원 문제(TSP)와 그 변종이며, 일반 TSP는 NP-난해다.
최근접 이웃의 발상은 그리디다 — "지금 서 있는 곳에서 가장 가까운, 아직 안 가본 지점으로 간다." 이것을 모든 지점을 방문할 때까지 반복한다. 매 단계가 단순한 최소값 찾기이므로 구현은 O(n²)(거리 표가 있으면)이고, 실전에서 최적해의 25% 이내로 떨어지는 경로를 대개 단번에 만들어 준다.
그러나 NN은 근시안적이다. 매 단계에서 가장 가까운 곳만 보느라, 가까운 지점들을 다 먹어 치우고 나면 멀리 떨어진 외딴 지점들이 막판에 남는다. 그러면 그 외딴 지점들을 잇느라 비싼 장거리 간선이 강제된다. §2는 이 직관을 정량화해 — metric TSP에서조차 NN의 근사비가 Θ(log n)까지 나빠질 수 있음을 보인다. 그리고 §3은 그 마지막 한 걸음의 손해를 국소탐색(2-opt/swap)으로 사후에 깎아내는 방법을 다룬다.
왜 "가장 가까운 곳"이라는 욕심이 때로 크게 빗나가는가? 그 답이 §2의 근사비 분석이다.
NN은 최적이 아니다 — 그것은 휴리스틱이다. 휴리스틱을 평가하는 척도는 근사비(approximation ratio) — "이 알고리즘의 해가 최적해보다 최대 몇 배 나쁠 수 있는가"이다. NN의 근사비는 좋지도, 절망적이지도 않다.
metric TSP에서 최근접 이웃 휴리스틱이 만드는 투어의 길이를 NN, 최적 투어의 길이를 OPT라 하면 NN / OPT ≤ ½(⌈log₂ n⌉ + 1). 또한 이 상한은 본질적으로 타이트하다 — NN / OPT = Θ(log n)이 되도록 만드는 입력족이 존재한다. NN은 상수 배 근사 알고리즘이 아니다.
각 노드 v에, NN이 v를 떠날 때(또는 v로 들어올 때) 쓴 간선 길이 a(v)를 할당하자. NN = Σ a(v).
핵심 보조 사실: 노드들을 a(v)가 큰 순서로 정렬하면, k번째로 큰 노드 v에 대해 a(v) ≤ 2·OPT / k가 성립한다. 직관은 — NN이 v에서 그렇게 긴 간선을 쓸 수밖에 없었다는 것은, 그 순간 가까운 곳에 미방문 노드가 없었다는 뜻이고, 따라서 a(v) 이상 떨어진 노드가 적어도 k개 모여 있어야 한다 — 그런 노드들을 최적 투어가 잇는 비용이 OPT의 하한을 준다.
이를 합치면 NN = Σₖ a(v_k) ≤ Σₖ 2·OPT/k = 2·OPT·Hₙ, 여기서 Hₙ = 1 + ½ + ⅓ + … ≈ ln n은 조화수다. 상수를 다듬으면 정리의 ½(⌈log₂ n⌉+1) 형태가 나온다.
근사비가 나빠지는 입력은 거의 항상 같은 모양이다 — NN이 가까운 노드들을 욕심껏 소진한 뒤, 유일하게 남은 외딴 노드로 가는 한 개의 매우 긴 간선을 강요받는다. 투어를 닫는 마지막 간선(출발점으로의 복귀)도 같은 함정을 판다 — 그 길이는 사전에 전혀 통제되지 않았다. 조화수의 발산은 이 "막판 장거리 간선"이 입력 크기에 따라 누적되며 생긴다. NN의 약점은 알고리즘 전체가 아니라 그 마지막 몇 걸음에 응축되어 있다 — 그래서 사후 국소탐색이 효과를 본다.
실전 라우팅은 두 단계다. (1) NN으로 초기 투어를 만든다 — 빠르고 그럴듯하다. (2) 2-opt로 다듬는다 — 투어에서 두 간선을 끊고, 사이 구간을 뒤집어 다시 이어 본다. 그 결과 투어가 짧아지면 채택한다. 더 이상 개선되는 2-opt 수가 없을 때 멈춘다(국소 최적). 2-opt는 평면 투어의 교차(자기 교차)를 제거하는 연산으로 해석할 수 있다 — 교차하는 두 간선은 삼각부등식에 의해 항상 풀어내는 게 이득이다.
#include <vector>#include <algorithm>#include <limits>using namespace std;using Matrix = vector<vector<double>>; // d[i][j]// ── 1단계: 최근접 이웃으로 초기 투어 ──vector<int> nearestNeighbor(const Matrix& d, int start) { int n = d.size(); vector<bool> used(n, false); vector<int> tour = { start }; used[start] = true; for (int step = 1; step < n; ++step) { int cur = tour.back(), next = -1; double best = numeric_limits<double>::max(); for (int v = 0; v < n; ++v) // 그리디 한 걸음 if (!used[v] && d[cur][v] < best) { best = d[cur][v]; next = v; } tour.push_back(next); used[next] = true; } return tour;}// 닫힌 투어의 총 길이 (마지막→처음 복귀 포함)double tourLen(const vector<int>& t, const Matrix& d) { double s = 0; for (size_t i = 0; i < t.size(); ++i) s += d[t[i]][t[(i + 1) % t.size()]]; return s;}// ── 2단계: 2-opt 국소탐색 — 교차 간선 제거 ──void twoOpt(vector<int>& t, const Matrix& d) { int n = t.size(); bool improved = true; while (improved) { // 국소최적까지 반복 improved = false; for (int i = 0; i < n - 1; ++i) for (int k = i + 1; k < n; ++k) { int a = t[i], b = t[(i + 1) % n]; int c = t[k], e = t[(k + 1) % n]; // 간선 (a,b),(c,e) → (a,c),(b,e) 로 교체 시 이득? if (d[a][c] + d[b][e] < d[a][b] + d[c][e] - 1e-9) { reverse(t.begin() + i + 1, t.begin() + k + 1); // 구간 뒤집기 improved = true; } } }}// 전체 라우팅: NN 초기해 → 2-opt 다듬기vector<int> route(const Matrix& d, int start) { auto tour = nearestNeighbor(d, start); twoOpt(tour, d); return tour;}
reverse로 통째로 뒤집어야 방향이 맞는다. 부등식의 -1e-9는 부동소수 오차로 인한 무한 루프를 막는 임계값이다. NN은 O(n²), 2-opt 한 번의 패스가 O(n²)이며 보통 O(n)회 미만의 패스로 국소최적에 수렴해 전체 O(n³) 안팎이다. swap(2-opt)은 NN의 막판 장거리 간선과 자기 교차를 직접 겨냥한다 — §2가 지목한 약점을 정확히 보강한다. 보강의 일반 이론은 국소탐색 원리에서 다룬다.
평면 metric에서 2-opt 국소최적 투어에는 자기 교차 간선이 없다. 두 간선이 교차하면, 삼각부등식에 의해 그 교차를 푸는 2-opt 이동이 항상 투어를 짧게 만들기 때문이다 — 따라서 교차가 남아 있는 투어는 국소최적일 수 없다. 다만 국소최적이 전역최적인 것은 아니다. 2-opt가 빠지는 국소최적의 품질과 그 탈출 전략은 국소탐색 원리의 주제다.
Expert의 라우팅 문제는 순수 TSP로 오지 않는다 — 픽업·배달의 선후 제약, 차량 용량, 시간창(time window)이 붙는 제약 라우팅이다. NN은 그 모든 변종의 공통 출발점이며, 제약은 "그리디 한 걸음"의 후보 집합을 좁히는 방식으로 흡수된다.
물류배송의 라우팅은 "TH(목적지)에서 픽업한 화물을 어딘가에 배달한다"는 선후 제약을 가진다 — 배달 지점은 그 픽업 지점을 이미 거친 뒤에만 방문 가능한 후보가 된다. NN의 argmin은 그대로 두되, 후보 집합 {v : !used[v]}에 "픽업 선행 조건을 만족함"이라는 필터를 한 겹 더 건다. 그리디 골격은 불변, 제약만 후보를 깎는다.
택시배정은 NN으로 각 택시–승객 매칭과 경로의 초기해를 잡은 뒤, swap 국소탐색으로 다듬는다 — 두 택시의 담당 승객을 맞바꾸거나, 한 경로 안에서 두 정차점의 순서를 뒤집어 본다. §2가 보였듯 NN의 손해는 막판에 응축되므로, swap은 그 응축된 손해를 사후에 정확히 겨냥해 깎아낸다. 여기서 swap이 "어느 균형을 맞추는가"는 국소탐색의 balancing 관점으로 이어진다.
배달기사에서 NN의 결과는 출발 노드에 민감하다 — 어디서 시작하느냐가 막판에 어떤 외딴 노드가 남는지를 좌우한다. 그래서 실전 트릭은 여러 출발점에서 NN을 각각 돌리고, 2-opt까지 적용한 뒤 가장 짧은 투어를 채택하는 것이다(multi-start). n이 작으면 모든 출발점을 시도해도 O(n⁴) 안에서 끝나며, NN의 Θ(log n) 최악 케이스에 빠질 확률을 크게 낮춘다.
| 방법 | 시간 | 근사 보장 | 쓰임 |
|---|---|---|---|
| Nearest Neighbor | O(n²) | Θ(log n) | 초기해 생성 — 가장 빠르고 단순 |
| 2-opt / swap | O(n²)/패스 | — | 초기 투어 다듬기 — 교차 제거 |
| Greedy Edge | O(n² log n) | Θ(log n) | 짧은 간선부터 — NN보다 평균 약간 우수 |
| Christofides | O(n³) | 3/2 | metric TSP의 최선 상수 근사 보장 |
| DP (Held–Karp) | O(2ⁿ·n²) | 최적 | n ≤ 약 20 — 정확해가 필요할 때 |
NN과 greedy-edge는 둘 다 Θ(log n) 근사로 보장은 약하지만, 빠르고 — 무엇보다 국소탐색의 좋은 출발점이라는 점에서 가치가 있다. Christofides는 metric TSP에서 3/2라는 상수 배 근사를 증명적으로 보장하는 유일한 고전 알고리즘이지만, 최소 신장 트리·최소 가중 완전 매칭·오일러 회로를 엮어야 해 구현이 무겁다 — Expert 시간 제약에서는 NN+2-opt가 실용적으로 더 자주 이긴다. n이 20 이하로 작으면 Held–Karp 비트마스크 DP로 정확해를 구하는 편이 낫다. 그리고 NN의 그리디 한 걸음이 옳은지 묻는 일은 그리디 교환논법의 영역이며 — NN에서는 그 교환논법이 실패한다는 사실이 곧 NN이 휴리스틱일 뿐이라는 증거다. 그 실패를 메우는 것이 국소탐색이다.