§ 1문제 정의
건물의 모든 방에서 쓰레기통까지의 평균 거리를 최소화하려면, k개의 쓰레기통을 어디에 둬야 할까? 이는 정확히 그래프 k-Median 문제이고, NP-hard로 알려져 있다.
그러나 |V| ≤ 200 정도라면, Floyd-Warshall로 모든 쌍 거리를 O(V³)으로 미리 계산해두면 이후 평가가 O(V × k)으로 매우 빠르다. 그리디로 초기 해를 만들고 1-swap local search로 개선하면 5-근사 해가 보장된다.
k-Median은 NP-hard지만, “전체 쌍 거리 캐시”라는 한 가지 사전 계산으로 local search가 빛난다.
§ 21-Swap Local Search 시뮬레이션
3개의 쓰레기통을 임의로 시작 → 한 곳을 빼고 다른 곳을 넣어봤을 때 총 거리가 줄어들면 교체. 더 줄어들 swap이 없으면 종료.
FIG. 19 — 1-swap improvement on k-median
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3왜 그리디 + 1-Swap이 최적인가
k-Median의 정확한 해는 NP-hard. 그러나 다음 접근법이 시간 대비 가성비 최고:
| 알고리즘 | 근사비 | 시간 |
|---|---|---|
| Brute Force (C(V,k)) | 1.0 (정확) | O(V^k) — k=20일 때 불가 |
| 그리디 (가장 멀리) | ~2x | O(V × k) |
| 그리디 + 1-Swap | 5x 보장 (실전 1.05x) | O(V² × k × iter) |
| LP relaxation | 3.25x | 구현 복잡 |
Arya-Garg 정리 (2001): p-swap local search는 (3 + 2/p)-근사. p=1이면 5-근사. 실전에서 1.05~1.1배 사이로 수렴.
Floyd-Warshall O(V³) 캐시의 가치: 1-swap 한 번 평가가 O(V) (각 노드별 최근 bin 갱신). N=200, k=10, 1000회 swap이면 약 2백만 연산. 1초 안.
사전계산이 클수록 local search가 싸진다. 모든 알고리즘 문제의 황금 공식.
§ 4알고리즘 골격
init(graph):
# 모든 쌍 최단거리 — Floyd-Warshall
dist[V][V] = INF
for (u,v,w) in edges: dist[u][v] = w
for k in 0..V: for i in 0..V: for j in 0..V:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
solve(k):
# 1) 그리디 초기해 — 가장 먼 점부터 추가
S = [random_node()]
while |S| < k:
v* = argmax_v (min_s∈S dist[v][s])
S.add(v*)
cost = sum_v min_s∈S dist[v][s]
# 2) 1-Swap Local Search
improved = True
while improved:
improved = False
for s_out in S:
for s_in in V - S:
newS = S - {s_out} + {s_in}
newCost = sum_v min_t∈newS dist[v][t]
if newCost < cost:
S, cost = newS, newCost
improved = True
break
if improved: break
return S, cost