근사 알고리즘

근사 알고리즘(approximation algorithm)은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다. 근사 알고리즘은 NP-완전 문제등 현재 알려진 빠른 최적화 알고리즘이 없을 문제에 대해 주로 사용된다.

근사 비율

어떤 최적화 문제에 대해, 항상 $\rho$배를 벗어나지 않는 근사해를 구하는 알고리즘이 존재할 경우, 그 알고리즘을 $\rho$-근사 알고리즘이라고 부른다. 즉, 최적해가 OPT일 경우, 근사 알고리즘 $f(x)$는 항상

• $\mathrm {OPT} (x)\leq f(x)\leq \rho \mathrm {OPT} (x)$ ($\rho >1$인 경우)
• $\rho \mathrm {OPT} (x)\leq f(x)\leq \mathrm {OPT} (x)$ ($\rho <1$인 경우)

를 만족해야 한다.

비 거리 공간 외판원 문제의 근사 불가능성

어떤 변에서는 삼각 부등식이 성립하지 않는 비 거리 공간 외판원 문제는 어떤 최적화 문제에 대해 항상 p배를 벗어나지 않는 근사해를 구하는 알고리즘이 모든 p에 대해 존재하지 않는다.

비 거리 공간 외판원 문제 G를 정의하자.

마찬가지로 해밀턴 회로 판단 문제 G를 정의하고 G로부터 완벽 그래프 G'을 V(G') = V(G)를 만족하도록 골라 가중치 w를 G에 포함된 변일 경우 1, 아닐 경우 kn을 부여한다.

이 때 "G에서 k 다항 시간 근사 해법을 찾을 수 있다"는 명제와 "G'에서 가중치가 kn보다 작은 해밀턴 경로를 찾을 수 있다"는 명제가 동치임을 증명한다.

G가 해밀턴 경로를 가지지 않는다면 모든 G'의 해밀턴 경로는 적어도 하나 이상의 G에 포함되지 않은 변을 사용해야하므로 가중치가 kn보다 크다.

G가 해밀턴 경로를 가진다면 G'에서도 가중치가 n인 같은 해밀턴 경로 T*를 찾을 수 있다. 그렇다면 다항 시간 근사 해법에 의하면 해밀턴 경로는 최대 k · w(T*) = kn 의 가중치를 가지게 된다.

따라서 비 거리 공간 외판원 문제 G의 근사 알고리즘이 존재한다면, 해밀턴 회로인지 판단하는 문제의 다항 시간 근사 해법이 존재하게 되어 NP-complete인 해밀턴 회로 판단 문제가 P임이 증명되었으므로 P=NP임이 증명되어 모순이다.

크리스토피데스 알고리즘

크리스토피데스 알고리즘은 거리 공간 외판원 문제에서 근사해를 구하는 근사 알고리즘이다. 위 근사 알고리즘은 최대 최적해의 3/2배 길이 안에 근사해를 구할 것을 보장하며, Nicos Christofides에 의해 1976년 개발되었다.

2017년까지도 특정 조건에서의 거리 공간 외판원 문제를 제외한 일반 거리 공간 외판원 문제를 해결하는 가장 좋은 근사해라고 알려져 있다.

같이 보기

• 다항 시간 근사 해법
• 근 찾기 알고리즘

참고 문헌

• 비제이 V. 바지라니 (2003). 《Approximation Algorithms》 (영어). 베를린: Springer. ISBN 3540653678.