근사 알고리즘

근사 알고리즘(近似 algorithm, Approximation algorithm)은 최적해(optimal solution)를 찾는 것이 계산적으로 매우 어렵거나 불가능한 경우, 주어진 문제에 대해 최적해에 가까운 해, 즉 근사해(近似解)를 다항 시간(polynomial time) 내에 효율적으로 찾는 알고리즘이다. 주로 NP-난해 문제(NP-hard problem)와 같은 조합 최적화 문제(combinatorial optimization problem)에 적용된다.

개요

많은 중요한 최적화 문제(예: 외판원 문제, 정점 덮개 문제, 배낭 문제)는 NP-난해 문제로 알려져 있다. NP-난해 문제는 P=NP 가 성립하지 않는 한, 문제의 크기에 대해 다항 시간 안에 최적해를 찾는 알고리즘이 존재하지 않는다고 여겨진다. 그러나 실제 응용에서는 최적해까지는 아니더라도 '충분히 좋은' 해를 비교적 짧은 시간 안에 얻는 것이 중요할 때가 많다. 근사 알고리즘은 이러한 요구를 충족시키기 위해 고안되었다.

근사 알고리즘은 발견한 해가 최적해와 얼마나 가까운지를 '근사율'(approximation ratio) 또는 '근사 요소'(approximation factor)라는 척도로 평가한다. 근사율은 알고리즘이 찾은 해의 비용(또는 가치)과 최적해의 비용(또는 가치) 사이의 비율로 정의된다. 근사율이 낮을수록 (최소화 문제의 경우) 또는 높을수록 (최대화 문제의 경우), 알고리즘의 성능이 더 좋다고 평가된다. 예를 들어, 근사율이 2인 최소화 문제 근사 알고리즘은 찾은 해의 비용이 최적해 비용의 두 배를 넘지 않음을 보장한다.

특징 및 목적

• 효율성: 대부분 다항 시간 내에 실행되도록 설계된다.
• 보장된 성능: 발견한 해의 품질이 최적해와 비교하여 어느 정도 수준인지를 근사율로 이론적으로 보장한다. 이는 단순히 좋은 해를 찾으려고 시도하는 휴리스틱(heuristic)과 구분되는 특징이다. 휴리스틱은 보통 이론적인 성능 보장이 없다.
• 실용성: 최적해가 필요 없거나 찾기 어려울 때 현실적인 시간 제약 하에 사용할 수 있다.

활용 분야

근사 알고리즘은 컴퓨터 과학뿐만 아니라 운영 연구, 인공지능, 산업 공학 등 다양한 분야에서 최적화 문제 해결에 활용된다.

• 그래프 문제 (정점 덮개, 집합 덮개, 최대 독립 집합 등)
• 스케줄링 문제
• 위치 선정 문제
• 데이터 마이닝 및 클러스터링

종류 및 기법

근사 알고리즘을 설계하는 다양한 기법이 있으며, 특정 문제의 구조에 따라 적절한 기법이 사용된다.

• 탐욕 알고리즘 (Greedy algorithm): 각 단계에서 지역적으로 최적인 선택을 하여 전체적인 근사해를 구성한다.
• 지역 탐색 (Local search): 현재 해에서 조금씩 변경하면서 더 좋은 해를 찾아 이동한다.
• 선형 계획법 완화 (Linear programming relaxation): 정수 계획 문제를 선형 계획 문제로 완화하고, 얻어진 해를 반올림하거나 다른 방법으로 정수해로 변환하여 근사해를 얻는다.
• 프라이멀-듀얼 접근법 (Primal-dual approach): 최적화 문제의 프라이멀 문제와 듀얼 문제를 함께 고려하여 근사 알고리즘을 설계한다.

한계

모든 NP-난해 문제에 대해 만족스러운 수준의 근사율을 갖는 다항 시간 근사 알고리즘이 존재하는 것은 아니다. 어떤 문제들(예: 일반적인 외판원 문제)에 대해서는 아주 나쁜 근사율(예: 문제 크기에 비례하는 근사율)을 갖는 알고리즘만 존재하거나, 특정 근사율을 갖는 알고리즘의 존재 자체가 P=NP를 함의하는 경우도 있다. 이러한 한계를 다루는 연구 분야를 비근사성 결과(inapproximability results)라고 한다.

관련 개념

• 최적화 문제 (Optimization problem)
• NP-난해 문제 (NP-hard problem)
• 최적 알고리즘 (Optimal algorithm)
• 휴리스틱 (Heuristic)
• PTAS (Polynomial-Time Approximation Scheme): 임의의 상수 ε > 0에 대해 (1+ε) 근사율을 갖는 다항 시간 알고리즘 군. ε에 대해 다항 시간이어야 함.
• FPTAS (Fully Polynomial-Time Approximation Scheme): PTAS 중에서 입력 크기와 1/ε 모두에 대해 다항 시간인 알고리즘.