근사 알고리즘으로 NP-난해 문제의 해를 구하는 방법

최적해 대신 보장 가능한 해를 택할 때

NP-난해 문제에서는 최적해 탐색 비용이 실무 제약을 넘기기 쉽다. 근사 알고리즘은 다항시간 안에 최적값과 일정 비율 이내의 해를 산출하는 방식으로 이 간극을 다룬다.

최소화 문제에서 α-근사는 알고리즘의 해값이 α·OPT 이하임을 뜻한다. 최대화 문제에서는 해값이 OPT/α 이상이어야 한다. Vertex Cover와 Traveling Salesman Problem(TSP)은 이 기준과 탐욕적 전략을 함께 살펴보기 좋은 문제다.

Vertex Cover는 그래프의 모든 간선을 덮는 최소 정점 집합을 찾는 문제이며, 무가중과 가중 버전 모두 NP-난해다. TSP는 모든 도시를 정확히 한 번 방문한 뒤 출발점으로 되돌아오는 최소 비용 순회를 찾는다. 삼각 부등식이 성립하는 Metric TSP에서는 강한 근사 보장을 기대할 수 있지만, 일반 TSP는 다항 근사가 불가하다(최신 정보 확인 필요).

보장 조건은 문제 구조에서 나온다

근사비를 분석할 때는 charging argument, 교환 논법, 삼각 부등식 같은 증명 기법을 활용한다. Vertex Cover의 2-근사와 Metric TSP의 2-근사, Christofides의 1.5-근사는 이런 분석으로 알려진 표준 결과다.

구현에서는 Greedy 선택 규칙, MST 기반 배가(doubling), Primal-Dual 방식이 자주 쓰인다. 서브모듈성, 메트릭 성질, 이분성처럼 문제에 내재한 구조에 맞춰 전략을 골라야 한다.

단순 Greedy는 O(|E|) 또는 O(n^2) 수준에서 동작하며, MST+DFS는 O(E log V) 또는 O(n^2)다. 대규모 입력에서도 선형·준선형 성능을 달성하기 쉽다.

TSP 근사 보장을 적용하려면 대칭성, 삼각 부등식, 연결성을 확인해야 한다. 가중 Vertex Cover에서는 Primal-Dual이 2-근사를 보장하지만 단순 Greedy에는 같은 보장이 없다.

Vertex Cover에서 미덮개 간선을 처리하는 방식

무가중 단순 그래프 G=(V, E)에서 아직 덮이지 않은 간선 (u, v)를 하나 고른다. 두 끝점 {u, v}를 해 집합에 넣고, u 또는 v에 닿는 모든 간선을 제거한다. 남은 간선이 없어질 때까지 반복하면 근사 해 C를 얻으며 |C| ≤ 2·OPT가 보장된다.

Metric TSP의 MST 기반 순회

대칭 거리 행렬과 연결 그래프를 입력으로 받고 삼각 부등식이 성립한다고 가정한다. 먼저 MST를 만든 뒤 DFS 전순회로 방문 순서를 생성한다. 방문 순서의 중복 노드는 shortcutting으로 건너뛰어 순회를 완성한다.

이 방식으로 얻은 경로 Π는 cost(Π) ≤ 2·OPT를 만족한다.

빠른 초안을 위한 최근접 이웃

거리 행렬만 주어졌을 때는 임의의 시작점에서 출발해, 아직 방문하지 않은 노드 가운데 가장 가까운 곳으로 이동하는 과정을 반복할 수 있다. 마지막에는 시작점으로 복귀한다.

최근접 이웃은 일반적으로 근사비를 보장하지 않지만 경험적 성능은 양호하다. 보장 조건이 충족되지 않거나 빠르게 초안을 만들어야 할 때 사용할 수 있다.

⤢✕

검증 가능한 구현 예시

Python 3.10+와 입력 검증을 전제로 한 소규모 예시다.

무가중 Vertex Cover의 2-근사 구현은 다음과 같다.

def vertex_cover_2approx(n, edges):
    # n: 정점 수(0..n-1), edges: (u,v) 리스트
    uncovered = set(tuple(sorted(e)) for e in edges)
    cover = set()
    while uncovered:
        u, v = next(iter(uncovered))
        cover.add(u); cover.add(v)
        to_remove = [e for e in uncovered if u in e or v in e]
        for e in to_remove:
            uncovered.discard(e)
    return sorted(cover)

# 예시
n = 5
edges = [(0,1),(1,2),(2,3),(3,4)]
print(vertex_cover_2approx(n, edges))  # 예: [1,2,3]

다음 구현은 Prim 알고리즘으로 MST를 만든 뒤 DFS 전순회와 shortcutting을 적용한다.

def tsp_mst_2approx(dist):
    # dist: 대칭 거리 행렬, dist[i][i]=0, 삼각 부등식 가정
    n = len(dist)
    if any(dist[i][i] != 0 for i in range(n)):
        raise ValueError("대각 원소 0 요구")
    # Prim MST
    in_mst = [False]*n
    key = [float('inf')]*n
    parent = [-1]*n
    key[0] = 0
    for _ in range(n):
        u = min((key[i], i) for i in range(n) if not in_mst[i])[1]
        in_mst[u] = True
        for v in range(n):
            if not in_mst[v] and dist[u][v] < key[v]:
                key[v], parent[v] = dist[u][v], u
    adj = [[] for _ in range(n)]
    for v in range(1, n):
        u = parent[v]
        if u == -1:
            raise ValueError("비연결 그래프")
        adj[u].append(v); adj[v].append(u)
    # DFS preorder
    visited = [False]*n
    order = []
    def dfs(x):
        visited[x] = True
        order.append(x)
        for y in adj[x]:
            if not visited[y]:
                dfs(y)
    dfs(0)
    # Shortcutting
    seen, tour = set(), []
    for v in order:
        if v not in seen:
            tour.append(v); seen.add(v)
    tour.append(tour[0])
    return tour

# 예시
dist = [
    [0, 2, 3, 3],
    [2, 0, 4, 3],
    [3, 4, 0, 2],
    [3, 3, 2, 0],
]
print(tsp_mst_2approx(dist))  # 예: [0,1,3,2,0]

최근접 이웃 Greedy는 다음처럼 경로를 만든다.

def tsp_nearest_neighbor(dist, start=0):
    n = len(dist)
    visited = [False]*n
    path = [start]; visited[start] = True
    cur = start
    for _ in range(n-1):
        nxt = min((dist[cur][v], v) for v in range(n) if not visited[v])[1]
        path.append(nxt); visited[nxt] = True
        cur = nxt
    path.append(start)
    return path

네트워크·라우팅·검증 업무에 적용하기

네트워크 모니터링과 점검 지점 선정에서는 링크 커버리지를 만족하는 최소 수의 포인트 선택을 Vertex Cover로 모델링할 수 있다. 장비 수와 비용 제약이 있을 때 2-근사 해로 빠른 배치안을 구한다.

라스트마일 배송이나 설비 점검 라우팅은 거리 행렬이 메트릭에 가까울 경우 MST 2-근사 또는 Christofides로 고품질 경로를 산출할 수 있다. 실시간 재라우팅에서는 최근접 이웃으로 초안을 만든 뒤 개선 휴리스틱을 적용한다.

테스트 케이스와 데이터 검증 커버리지 역시 제약 위반 엣지를 덮는 문제로 볼 수 있다. 최소 테스트 포인트를 선정하는 데 Greedy 2-근사를 사용하면 시간을 단축할 수 있다.

Vertex Cover는 최적 대비 최대 2배 내 해를 보장하며, 수십만 엣지 규모에서 수 초 내 해를 산출할 가능성이 있다. Metric TSP는 2-근사로 최적 대비 ≤ 2배 경로 길이를 보장하고, Christofides를 사용하면 추가 구현 비용을 수반하는 1.5-근사를 적용할 수 있다. 최근접 이웃은 O(n^2) 시간으로 실시간 의사결정을 지원하며, 로컬 서치와 결합하면 초기 해 대비 20~40% 개선을 기대할 수 있다(경험치).

해 품질에 대한 이론적 신뢰성을 확보하면서 구현 단순성과 운영 편의를 높여 시스템 유지보수를 수월하게 만드는 것이 이 접근의 장점이다.

선택 기준을 비교하면

알고리즘	성능(시간복잡도)	확장성	일관성(근사비)	안정성	운영 편의
Vertex Cover Greedy 2-근사	O(E)	매우 높음	2-근사 보장	입력 순서에 둔감	매우 단순
Metric TSP MST 2-근사	O(E log V) 또는 O(n^2)	높음	2-근사 보장(삼각 부등식)	전제 충족 시 안정	단순(MST+DFS)
TSP 최근접 이웃	O(n^2)	중간	보장 미약(최악 비유계)	시작점 민감	매우 단순

적용 전에는 전제 조건을 확인하고, 품질과 시간의 트레이드오프에 맞춰 선택해야 한다. 전처리로 조건을 점검한 뒤 빠른 Greedy 초안을 만들고, MST나 Christofides 같은 구조적 근사를 적용하며, 필요하면 국소 개선을 옵션으로 더하는 흐름을 사용할 수 있다.