최적해를 단번에 구성할 수 없을 때, 국소탐색은 다른 길을 택한다 — 일단 아무 해나 들고, 그 "이웃"을 살펴 조금이라도 나은 해로 한 걸음씩 옮긴다. 이웃을 어떻게 정의하느냐가 알고리즘의 전부이며, 멈추는 곳이 국소최적이다. 놀랍게도 이 단순한 발상은 — 이웃만 잘 정의하면 — 증명 가능한 근사비를 낳는다. 이 페이지는 국소탐색의 일반 틀을 세우고, k-Median을 1-swap 국소탐색으로 푸는 Arya–Garg의 (3 + 2/p)-근사 정리를 다룬다.
국소탐색은 알고리즘이라기보다 설계 틀(meta-heuristic)이다. 어떤 최적화 문제든 — 해 공간 위에 "이웃 관계"를 정의할 수 있으면 — 같은 골격으로 풀 수 있다.
틀은 네 부품으로 이루어진다. (1) 해 표현: 무엇을 한 개의 해로 볼 것인가(투어 하나, 시설 위치 집합 하나). (2) 이웃(neighborhood) 정의: 한 해에서 "한 번의 작은 수정"으로 도달 가능한 해들의 집합 — 국소탐색의 성패가 거의 전적으로 여기에 달려 있다. (3) 이동 규칙: 이웃 중 더 나은 해가 있으면 그리로 옮긴다(개선이 가장 큰 곳으로 가는 steepest, 첫 개선으로 가는 first-improvement). (4) 종료 조건: 이웃에 더 나은 해가 하나도 없으면 멈춘다 — 그 해가 국소최적(local optimum)이다.
국소최적은 전역최적이 아닐 수 있다 — 이웃이라는 좁은 창으로만 세상을 보기 때문이다. 그래서 국소탐색에는 두 개의 긴장이 흐른다. 하나는 "이웃을 얼마나 넓게 정의할 것인가" — 넓으면 더 좋은 국소최적에 닿지만 한 걸음의 비용이 커진다. 다른 하나는 국소최적을 어떻게 빠져나갈 것인가(escape) — 무작위 재시작, 담금질(simulated annealing), tabu search 등이 답이다.
놀라운 점은 — 이웃을 영리하게 정의하면, 국소탐색이 단지 "그럭저럭"이 아니라 증명 가능한 근사비를 낳는다는 것이다. §2가 그 대표 사례인 k-Median을 다룬다.
k-Median에 국소탐색을 적용하려면 이웃을 정의해야 한다. 가장 단순한 선택 — 1-swap: 현재 시설 집합 S에서 시설 하나를 빼고, 시설이 아닌 위치 하나를 넣는다. |S| = k는 유지된다. 더 일반적으로 p-swap은 한 번에 최대 p개를 맞바꾼다.
metric k-Median에서, p-swap 이웃의 국소최적해 S의 비용은 최적해 비용 OPT에 대해 cost(S) ≤ (3 + 2/p) · OPT를 만족한다. 특히 1-swap 국소최적은 5-근사(p=1)이고, p를 키우면 근사비가 3으로 수렴한다. 이 한계는 본질적으로 타이트하다.
S가 1-swap 국소최적이라는 사실은 — 어떤 swap도 비용을 줄이지 못한다는 부등식의 다발이다. 증명의 전략은 이 "개선 없음" 부등식들을 영리하게 골라 합산해, cost(S) ≤ 5·OPT를 짜내는 것이다.
최적해의 시설 집합을 O라 하자. O의 각 시설 o를 S의 시설 하나에 — 일종의 매칭으로 — 대응시킨다. 각 대응쌍에 대해 "S의 그 시설을 빼고 o를 넣는 swap"을 가상으로 수행한다. 국소최적이므로 이 swap의 비용 변화는 ≥ 0이다.
이 swap 후 수요점들을 재배정할 때 — 삼각부등식이 결정적으로 쓰인다. 새 시설 o를 잃은 수요점은 그 근처의 다른 S 시설로 우회하는데, 그 우회 비용을 삼각부등식으로 cost(S)와 OPT의 항으로 묶을 수 있다. k개의 swap 부등식을 모두 더하면, 좌변에 cost(S)가, 우변에 OPT의 상수배가 남아 — 정리하면 cost(S) ≤ 5·OPT. p-swap에서는 한 번에 p개를 묶어 더 촘촘한 부등식을 만들 수 있어 상수가 3 + 2/p로 개선된다.
국소탐색의 일반적 약점은 "국소최적이 전역최적에서 임의로 멀 수 있다"는 것이다 — 그런데 §2의 정리는 그렇지 않다고 말한다. k-Median의 1-swap 국소최적은 전역최적의 5배 이내임이 보장된다. 이것이 국소탐색의 진짜 힘이다 — 이웃을 문제 구조에 맞게(여기서는 metric 구조에 맞게) 정의하면, "더 나은 이웃이 없다"는 사실 자체가 비용 상한을 증명하는 재료가 된다. 임의의 휴리스틱이 아니라, 증명 가능한 근사 알고리즘인 것이다.
아래는 k-Median 1-swap 국소탐색의 골격이다. 핵심은 두 부분 — cost: 시설 집합이 주어졌을 때 모든 수요점을 가장 가까운 시설에 배정한 총 거리. localSearch: 모든 (빼낼 시설 × 넣을 후보) 쌍을 훑어 개선이 있으면 적용하고, ε-개선 임계값으로 종료를 보장한다.
#include <vector>#include <algorithm>#include <limits>using namespace std;using Matrix = vector<vector<double>>; // d[client][site]// 시설 집합 S 에 대한 총 서비스 비용// = Σ_client min_{s∈S} d[client][s]double cost(const vector<int>& S, const Matrix& d) { double total = 0; for (size_t c = 0; c < d.size(); ++c) { double best = numeric_limits<double>::max(); for (int s : S) best = min(best, d[c][s]); total += best; } return total;}// 1-swap 국소탐색: site 한 개를 빼고 다른 한 개를 넣음vector<int> localSearch(vector<int> S, int numSites, const Matrix& d, double eps) { vector<bool> inS(numSites, false); for (int s : S) inS[s] = true; double cur = cost(S, d); bool improved = true; while (improved) { // 국소최적까지 improved = false; // 이웃 N(S): 모든 (빼낼 i) × (넣을 a) 쌍 for (size_t i = 0; i < S.size() && !improved; ++i) for (int a = 0; a < numSites; ++a) { if (inS[a]) continue; // 이미 시설 int out = S[i]; S[i] = a; // 가상 swap double cand = cost(S, d); // epsilon-개선: 충분히 줄어들 때만 채택 if (cand < cur * (1.0 - eps)) { inS[out] = false; inS[a] = true; cur = cand; improved = true; // 첫 개선 즉시 적용 } else { S[i] = out; // 되돌리기 } } } return S; // (3+2/p+ε)-근사 보장}
cand < cur*(1−eps)가 §2 pitfall에서 말한 ε-개선 임계값 — 미미한 개선을 무시해 반복 수를 다항식으로 묶고, 그 대가로 근사비를 (3+2/p)에서 (3+2/p+ε)로 양보한다. 라인 39의 improved = true 직후 바깥 루프 조건 !improved가 작동해 first-improvement(첫 개선 즉시 적용) 전략이 된다 — steepest descent를 원하면 모든 쌍을 다 본 뒤 최선을 적용하도록 바꾼다. cost는 O(n·k), 한 패스가 O(n·k·numSites)다. 1-swap을 p-swap으로 키우려면 라인 28–29를 "p개를 빼고 p개를 넣는" 조합 루프로 확장한다 — 근사비는 3에 가까워지지만 이웃 크기가 numSites^p로 폭발하므로 p는 작게(2~3) 둔다.
한 번의 이웃 탐색 패스는 O(n · k · numSites)(각 후보 swap마다 cost 재계산). ε-개선 임계값이 없으면 반복 수에 다항 상한이 없지만, 임계값을 두면 비용이 매 채택마다 적어도 (1−ε)배로 줄어 — 초기 비용 대비 O((1/ε)·log(cost₀/OPT))회의 채택 안에 국소최적에 닿는다. 전체적으로 다항시간 (3+2/p+ε)-근사가 보장된다. 메모리는 거리 행렬 O(n · numSites)가 지배적이다.
Expert 문제에서 국소탐색은 "이웃을 무엇으로 잡을 것인가"라는 한 가지 결정으로 모습을 완전히 바꾼다. 같은 골격(§3)에 다른 이웃을 끼우면 다른 알고리즘이 된다.
쓰레기통은 k-Median의 거의 교과서적 사례다 — k개의 쓰레기통 위치를 골라, 모든 가구에서 가장 가까운 쓰레기통까지의 거리 합을 최소화한다. §3의 1-swap 국소탐색을 그대로 얹으면 (3+2/p)-근사가 즉시 따라온다. 여기서 §2의 정리가 주는 선물은 — 단지 "답이 나온다"가 아니라 "그 답이 최적의 5배(혹은 더 좋게) 이내임이 증명되어 있다"는 점이다. 채점 데이터가 적대적이어도 근사비 보장은 깨지지 않는다.
택시배정의 swap 국소탐색은 비용 최소화이면서 동시에 balancing — 여러 택시에 승객/거리 부하를 고르게 분산 — 의 성격을 띤다. 이웃을 "두 택시의 담당 승객 하나씩을 맞바꾸기"로 정의하면, 한 택시가 과부하인 국소해에서 swap이 부하를 옮겨 더 균형 잡힌 국소최적으로 내려간다. NN으로 만든 초기해가 이 국소탐색의 출발점이 된다 — NN은 초기해 생성기, 국소탐색은 다듬개라는 §3의 분업이 여기서 실현된다.
국소최적에 갇히는 문제는 이웃을 넓히거나 escape를 더해 푼다. multi-start(여러 초기해에서 각각 국소탐색 후 최선 채택)는 가장 단순한 escape이고, p-swap으로 이웃을 키우면 더 좋은 국소최적에 닿는다(§2의 근사비가 p와 함께 개선되는 것이 그 이론적 근거다). 그리디 교환논법이 "한 번의 교환으로 최적해를 그리디로 민다"였다면, 국소탐색은 그 교환을 해 공간 전체에 풀어 — 증명이 막힌 곳에서도 근사적으로 작동하게 만든 일반화다.
| 방법 | escape | 근사 보장 | 쓰임 |
|---|---|---|---|
| 1-swap Local Search | 없음 | (3+2/p) | k-Median·시설 배치 — 증명 가능한 근사 |
| Multi-start | 재시작 | — | 국소최적 회피의 가장 단순한 보강 |
| Simulated Annealing | 확률적 악화 허용 | — | 거친 비용 지형 — 온도 스케줄로 escape |
| Tabu Search | 최근 이동 금지 | — | 국소최적 주변 순환을 끊어야 할 때 |
| LP-rounding / Primal-Dual | — | 상수배 | k-Median에 더 작은 상수 — 구현은 무겁다 |
국소탐색 자체는 escape 장치가 없어 첫 국소최적에서 멈춘다 — 그런데 k-Median 1-swap처럼 이웃이 문제 구조와 맞물리면 그 국소최적조차 증명된 근사비를 가진다는 것이 이 계열의 백미다. escape가 필요하면 multi-start가 가장 싸고, 비용 지형이 험하면 담금질이 확률적으로 언덕을 넘으며, 국소최적 주변을 맴도는 순환이 문제면 tabu search가 최근 이동을 금지해 끊는다. 이들은 근사 보장은 없지만 실전 품질이 좋다. 더 작은 상수의 증명된 근사가 필요하면 LP-rounding이나 primal-dual로 가지만 — Expert의 시간·구현 제약에서는 §3의 30줄짜리 1-swap이 거의 항상 실용적으로 이긴다. NN의 2-opt도 본질은 국소탐색(투어 공간의 이웃) — 두 원리는 같은 틀의 두 사례다. 그리고 그리디 교환논법의 "한 번의 교환"을 해 공간 전체에 일반화한 것이 바로 국소탐색이다.