[ Algorithm ] 근사 알고리즘

 

다항식 시간보다 큰 복잡도를 가진 알고리즘으로 해결되는 문제의 집합.

 

여러 가지 문제 집합으로 다시 분류.

 

NP-완전 문제의 특성

 

어느 하나의 NP-완전 문제에 대해서 다항식 시간의 알고리즘을 찾아내면

(다항식 시간에 해를 찾을 수 있으면) 모든 다른 NP-완전 문제도 다항식 시간에 해를 찾을 수 있다.

 

NP 문제 집합

 

P 문제 집합과 NP-완전 문제 집합을 둘 다 포함하는 문제의 집합

 

NP 알고리즘

 

비결정적 다항식 시간 알고리즘

 

1단계 : 주어진 입력에 대해서 하나의 해 추측하기

2단계 : 그 해를 다항식 시간에 확인한 후에 그 해가 '맞다/아니다'라고 답한다.

 

 

따라서 NP 알고리즘은 정해진 시간복잡도를 갖는 것이 아니라,

해를 추측하는 것이다.

 

 

정리하자면,

NP 알고리즘은 해를 찾는 알고리즘이 아니라 해를 다항식 시간에 확인하는 알고리즘이다.

 

 

 

통 채우기 문제

 

통 용량이 C 일때 n 개의 물건을 가장 적은 수의 통에 채우는 문제.

단, 각 물건의 크기는 C보다 크지 않다.