근사 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

근사 알고리즘(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인 경우)

를 만족해야 한다.

더 보기[편집]

참고문헌[편집]