[알고리즘] 휴리스틱 알고리즘

우리가 문제 해결 시에 사용하는 동적 계획법(DP) 또는 분할 정복과 같은 완전 탐색에 기초한 디자인 패러다임은 

실생활에서 사용하기 매우 한정적이다. 

 

예를들어, 인공지능 체스 프로그램을 브루트 포스 방식으로 짠다면 이동 가능한 모든 말의 움직임을 다 확인한다. 

 

하지만 이 방법으로 개발한다면 말과 이동할 수 있는 칸이 너무 많기 때문에, 게임이 끝나지 않는다고 한다.

(경우의 수가 10^120 가지)

 

결국 모든 경우의 수를 확인하지 않고도 답을 찾아낼 수 있는 방식을 사용해야 한다. 

 

휴리스틱 알고리즘이란? 

불충분한 시간이나 정보로 인해 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않을 

경우 보다 빠르게 사용할 수 있는 추론의 방법이다.

 

기본적으로 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어서 답의 수를 줄이는 것을 목표로 한다. 

 

휴리스틱 관련 이론 

˙ 가지치기 (pruning) 기법 

˙ 담금질 (Simulated Annealing) 기법

˙ 유전(Genetic) 알고리즘

 

정도가 있다.