지식
Algorithm

근사 알고리즘: 최적을 포기하고 보장을 얻다

NP-난해 최적화 문제를 다항 시간에 다루는 근사 알고리즘을 정리합니다. 근사 비율의 정의와 최소화·최대화에서의 의미, 정점 덮개 2-근사와 그리디 집합 덮개의 분석, PTAS와 FPTAS의 계층, 근사 불가능성까지 직관과 함께 다룹니다.

· 7 min read · PALDYN Team

지난 글에서 환원을 통해 수많은 문제가 NP-완전이라는 사실을 확인했습니다. 그렇다면 실무에서 정점 덮개나 외판원 같은 NP-난해 최적화 문제를 만나면 어떻게 해야 할까요? “다항 시간에 최적해를 못 구한다”는 사실 앞에서 포기할 수는 없습니다. 한 가지 현실적인 타협이 근사 알고리즘(approximation algorithm)입니다. 최적해를 정확히 구하려는 욕심을 내려놓는 대신, “최적에서 얼마나 벗어날 수 있는지”에 대한 수학적 보장을 다항 시간에 얻는 전략입니다.

근사 비율이란

근사 알고리즘의 품질은 근사 비율(approximation ratio) ρ로 측정합니다. 어떤 입력에서든 알고리즘이 내는 해의 비용 ALG와 최적 비용 OPT의 비율이 ρ를 넘지 않도록 보장하는 것이 핵심입니다.

근사 비율의 개념

최소화 문제에서는 ALG ≤ ρ · OPT (ρ ≥ 1)를, 최대화 문제에서는 ALG ≥ OPT / ρ를 보장합니다. ρ가 1에 가까울수록 좋은 알고리즘이며, ρ = 1이면 사실상 최적해입니다. 중요한 것은 이 보장이 운 좋은 입력 하나가 아니라 모든 입력에서 성립한다는 점입니다. 평균이 아니라 최악의 경우를 못 박는 것이 근사 비율의 정의입니다.

최소화:  ALG(I) ≤ ρ · OPT(I)    for all I
최대화:  ALG(I) ≥ OPT(I) / ρ    for all I
ρ 는 입력에 무관한 상수(또는 입력 크기의 함수)

정점 덮개 2-근사

가장 우아한 예시는 정점 덮개(vertex cover)입니다. 그래프의 모든 간선을 적어도 한 끝점이 덮도록 하는 최소 정점 집합을 찾는 문제로, NP-난해입니다. 그런데 놀랍도록 단순한 알고리즘이 2-근사를 보장합니다.

정점 덮개 2-근사 동작

아직 덮이지 않은 간선을 아무거나 하나 고르고, 그 양 끝점을 모두 덮개에 넣습니다. 이 과정을 모든 간선이 덮일 때까지 반복합니다.

def vertex_cover_2approx(edges):
    cover = set()
    covered = set()
    for u, v in edges:
        if (u, v) in covered:
            continue
        # 양 끝점을 모두 추가
        cover.add(u)
        cover.add(v)
        # u 또는 v 에 닿는 모든 간선이 덮였다
        for e in edges:
            if e[0] in (u, v) or e[1] in (u, v):
                covered.add(e)
    return cover

왜 2-근사일까요? 우리가 고른 간선들은 서로 끝점을 공유하지 않으므로 하나의 매칭(matching)을 이룹니다. 이 매칭의 각 간선을 덮으려면 최적해도 최소 한 개의 정점을 써야 하므로 |매칭| ≤ OPT입니다. 우리는 간선마다 정점을 2개씩 넣었으니 |cover| = 2·|매칭| ≤ 2·OPT. 단순한 그리디가 OPT의 2배를 절대 넘지 않는다는 강력한 보장을 줍니다.

그리디와 집합 덮개

모든 문제가 상수 비율로 풀리지는 않습니다. 집합 덮개(set cover)에서 가장 많은 미덮개 원소를 덮는 집합을 매번 고르는 그리디는 Hₙ ≈ ln n 비율을 보장합니다. 즉 비율이 입력 크기에 따라 로그로 커집니다. 흥미롭게도 이는 거의 최선입니다 — (1-ε)ln n보다 좋은 근사는 P = NP가 아닌 한 불가능하다는 것이 알려져 있습니다.

def set_cover_greedy(universe, subsets):
    uncovered = set(universe)
    chosen = []
    while uncovered:
        # 미덮개 원소를 가장 많이 덮는 집합 선택
        best = max(subsets, key=lambda s: len(s & uncovered))
        chosen.append(best)
        uncovered -= best
    return chosen

PTAS와 FPTAS

어떤 문제는 ρ를 우리가 원하는 만큼 1에 가깝게 조절할 수 있습니다. 임의의 ε > 0에 대해 (1+ε)-근사를 다항 시간에 주는 알고리즘 군을 PTAS(다항 시간 근사 스킴)라 부릅니다. 정밀도를 높일수록 시간이 늘지만, 입력 크기에 대해서는 여전히 다항입니다.

그중에서도 실행 시간이 1/ε에 대해서도 다항인 경우를 FPTAS라 합니다. 배낭 문제가 대표적으로, 값을 ε에 맞춰 반올림한 뒤 DP를 돌려 (1+ε)-근사를 효율적으로 얻습니다. 정리하면 근사 가능성에는 다음과 같은 계층이 있습니다.

FPTAS  ⊂  PTAS  ⊂  상수 비율  ⊂  log/poly 비율  ⊂  근사 불가
(쉬움)                                              (어려움)
배낭     일부기하   정점덮개      집합덮개         일반 TSP

근사에도 벽은 있다

근사가 만능은 아닙니다. 일반적인 외판원 문제(삼각 부등식 없음)는 상수 비율 근사조차 NP-난해입니다 — 어떤 상수 ρ로도 근사할 수 없습니다. 반면 삼각 부등식을 만족하는 거리 공간에서는 크리스토피데스 알고리즘이 1.5-근사를 줍니다. 같은 “외판원”이라도 입력 가정에 따라 근사 가능성이 천지차이라는 점이 근사 이론의 깊이를 보여줍니다.

근사 알고리즘은 NP-난해라는 벽 앞에서 “정확성”이라는 차원을 양보해 “다항 시간”과 “보장”을 동시에 얻는 길입니다. 다음 글에서는 또 다른 양보 — 무작위성을 도입해 기대 성능을 끌어올리는 무작위 알고리즘을 살펴봅니다.

지난 글: 환원: 문제의 어려움을 옮기는 기술

다음 글: 무작위 알고리즘: 동전을 던져 더 빨라지다


읽어주셔서 감사합니다. 😊