[알고리즘] Approximation Algorithm 이란 / NP 문제 알고리즘

Approximation Algorithm 이란

 

세상에는 무수한 문제들이 있고, 그 만큼 어려운 문제도 무수히 많다. (ex. NP문제)
알고리즘적으로 보통 어려운 문제는 polynomial 시간 안에 풀 수 없는 문제들을 말한다.
이들을 프로그래밍 적으로 사용하기에는 과부하가 너무 크다.
따라서, 완벽한 답을 구하는 것에는 살짝 내려놓고, 조금은 틀릴 수 있는 가능성이 있더라 하더라도 근접한 답을 구해낼 수 있는 빠른 알고리즘(polynomial 시간안에 해결이 가능한)을 택하는 것이다.
 
예를들자면, 우리가 인터넷으로 성능대비 가격이 좋은 컴퓨터를 사려고한다. 가장 좋은 방법은 온라인 상에 있는 모든 웹 사이트에 판매중인 컴퓨터 제품들을 하나하나 다 비교하고, 최고 가성비의 제품을 사는 것이다. 하지만, 현실적으로 그것은 불가능하고 시간 상으로도 손해이다. 따라서 일반적인 우리는 가격 비교 사이트를 이용해 비교적 값 싼 컴퓨터를 구매한다.
여기서는 가격비교 사이트 를 이용하는 것을 Approximation Algorithm 을 이용하는 것이라 할 수 있다.

 

---

Performance ratios of Approximation Algorithm

 

Performance ratios란 Approximation Algorithm 의 성능의 단위 이다.
Approximation Algorithm 이 얼마나 최적 해에 근접해 있는가를 나타낸다!
 
n - approximation Algorithm 이라고 표현 한다.
ex)  2-approximation Algorithm  기존의 최적해보다 2배 이내의 정확도는 만들어낸다.
      가령, Vertex-Cover 문제에서 , 최적의 상황은 vertex 3개로 cover 가 가능한 문제가 주어 졌을 때
      이 알고리즘을 이용하면 최고 3개 ~ 6개 까지의 답은 도출해 낸다는 뜻이다.
 
(1+E) approximation Algorithm
-> E가 커지면 커질수록 결과값이 부정확하기에 사용하기가 껄끄러워진다.
-> E가 작아지면 작아질수록 계산복잡성이 올라간다. (어렵다)
-> E가 0 에 수렴할 때가 제일 정확한 결과를 가진다.