다항식 시간 근사화 방식
0-1 배낭 문제 또는 부분집합 문제와 같은 NP-완전 문제에 대한 다항식 시간 솔루션을 찾을 수 있습니다. 이러한 문제는 실제 세계에서 매우 인기가 있으므로 이러한 문제를 처리할 몇 가지 방법이 있어야 합니다.
PTAS(Polynomial Time Approximation Scheme)는 최적화 문제에 대한 알고리즘을 근사화하는 유형입니다. 0-1 배낭 문제의 경우 의사 다항식 솔루션이 있지만 값이 크면 솔루션이 실현 가능하지 않습니다. 그렇다면 PTAS 솔루션이 필요합니다.
그래프 채색, K-중심 문제 등과 같은 일부 NP-완전 문제에는 알려진 다항식 시간 솔루션이 없습니다. PTAS 알고리즘을 근사화하는 데 사용됩니다. 이 알고리즘은 매개변수 ε> 0을 취하며 근사화하기 위해 최소화(1 + ε) 및 최대화(1 - ε)합니다.
예시
예를 들어, 최소화 문제를 선택하고 ε =0.5를 취하면 PTAS를 사용한 솔루션은 거의 1.5입니다. 따라서 실행 시간은 n의 관점에서 다항식이어야 하지만 ε의 관점에서 지수적일 수 있습니다.