휴리스틱(Heuristic)

어떠한 문제를 해결하기 위해 사용되는 규칙 또는 방법으로, 최적의 해를 찾는데 도움이 되는 추정치를 의미한다.

 

전체 탐색 공간을 줄이고, 계산비용을 낮추기 위해 사용되며, 일반적으로 근사값을 제공하게 된다.

 

휴리스틱 함수는 다음 두가지 특성을 가져야 한다.

 

1. 가능한 실제비용을 넘기지 말아야 한다.
   • 휴리스틱 함수는 실제 비용보다 작거나 같아야 한다. 즉, 휴리스틱이 실제 비용을 과하게 추정하지 말아야 한다.
2. 계산이 빠르고 간결해야 한다.
   • 휴리스틱 함수는 빠르게 계산되어야 한다. 만약, 계산시간을 합쳤을 때 그냥 가는거보다 느리다면, 그냥 이동시키는게 더 낫기 때문이다.