NP-complete

목차

없음

본문내용

P (Polynomial) & NP (Non-Polynomial)

대다수 문제는 크게 두 가지로 분류된다.

1. Polynomial Time Complexity 안에 풀 수 있는 알고리즘을 가진 문제( P )
즉, P : Polynomial Complexity를 갖는 알고리즘
2. Polynomial Time Complexity 안에 있는 알고리즘을 가지고 있지 않은 문제( NP )
즉, NP : Non-Polynomial(Exponential) Complexity를 갖는 알고리즘 어떠한 문제가 있다면 이 문제를 풀기 위한 여러 기법을 개발하게 되는데 현재까지 Polynomial type으로 이 문제를 푸는 기법이 나오지 않은 문제를 NP 문제라고 한다. 이 문제들은 Polynomial 기법이 발견되지 않은 것이지 할 수 없다는 것은 아니다.

<중 략>

하지만 휴리스틱 해법은 그 적용대상이 특정한 문제에 한정되고, 문제에 따른 그 해법의 구축도 용이하지 않다는 문제점을 지니고 있다. 따라서 이러한 문제점을 극복하기 위하여 Genetic Algorithm(유전자 알고리즘)의 응용이 효과적일 수 있다. GA란 최적해의 탐색과정에서 습득한 지식을 바탕으로 adaptive한 탐색을 계속해 나갈 수 있는 특성을 지닌 일종의 지능형 탐색기법으로, 생태계의 적자생존 및 유전자의 원리에 바탕을 두고 있다. 그 기법의 강력함이나 광범위한 응용가능성으로 인해 외국의 경우 생물학, 컴퓨터공학, 이미지 처리 및 패턴인식, 엔지니어링, OR, 사회과학 등 광범위한 분야에서 응용되고 있다. GA는 unimodal 문제로부터 multimodal 문제, 그리고 combinatorial 문제에 이르기까지 광범위한 문제영역에 걸쳐 좋은 해를 제공하는 것으로 발표되고 있다. 또한 다양한 최적화 문제에 일관성 있는 적용이 가능하며, 또한 문제의 상황이 변하더라도 코딩내용의 수정으로 GA의 계속적인 적용이 가능하여 휴리스틱 해법의 한계를 극복하고 있다.

참고 자료

없음