알고리즘설계기법 - 7. 근사해법

알고리즘과 복잡도

- 복잡도가 O(n) 처럼 작은 경우가 있지만 복잡도가 매우 큰 알고리즘도 많음

 

NP 완비 문제

- 풀기 쉬운지 어려운지도 모르는 문제들

 

P 문제

- 결정론적 알고리즘 deterministic algorithm으로 다항식 시간에 해결할수 있는 문제

- 결정론적 알고리즘 : 명확하게 결정되어있어 데이터 입력시 어느 순서대로 동작하는지 알수있는 알고리즘

 

NP 문제

- 비결정론적 알고리즘 nondeterministic algorithm으로 다항식 시간에 해결할수 있는 문제

- 비결정성 알고리즘 : 결정 가능한 경우가 여러개로 나뉘어져 적당한 경로러 선택해 나가는 알고리즘

=> 가장 적절한 경로를 잘 선택한 경우 다항식 시간으로 해를 찾을수 있는 문제를 NP 문제라 부름

 

 

근사 알고리즘 approximation algorithm

- NP문제는 최악의 경우 복잡도가 지수적으로 됨.

 => 최적해는 아니더라도 최적해에 가깝기만 하면 됨.

- 최적해에 가까운 근사해를 구하는 (결정론적) 알고리즘

 

 

휴리스틱 알고리즘

- 해를 얻을때까지 경험해가는 알고리즘

- 최적해의 계산 비용이 크고, 근사해로도 충분한 경우 사용

 

 

https://optimization.mccormick.northwestern.edu/index.php/Heuristic_algorithms