휴리스틱(Heuristic, 발견법)이란...

SPF 알고리즘중 휴리스틱 탐색을 보다가 휴리스틱 이야기가 나와서 검색해보니 위키피디아보다 더 알기쉽게 설명해놓은 곳이 있어 욕심을 내서 가져왔습니다.

Heuristic 은 그리스어 "heutiskein" 가 어원이며 "to discover" 라는 의미를 가진다. 즉 이미 정립된 공식에 의해서가 아니라, 정보가 완전하지 않은 상황에서 노력을 통해서 시행착오 (trial and error) 를 거처, 또는 경험을 통해서 주먹구구식의 규칙 (Rule of Thumb) 을 통해 지식을 알게되는 과정을 의미한다. 잘 추측하는 기술 (art of good guessing) 이라고 표현하기도 한다

명 의라고 소문난 대부분의 의사가 진단을 할 때 몇가지 핵심되는 내용에 대한 문진과 병리 자료로서 진단을 한다. 그리고 대부분 정확하다. 그가 진단할 때 매번 의학도 시절부터 배운 엄청난 양의 지식을 되새기지 않아도 그는 그동안의 진료 경험으로 진단을 수행한다. 그러나 간혹 조기 진단해야 할 암을 발견해 내지 못해 곤란을 겪기도 한다. 초보 운전자가 가장 어려움을 겪는 것은 좁은 주차장에서의 주차이다. 숙련된 운전사는 놀라우리 만한 감각으로 정확하게 주차시킨다. 무인 자동차가 그렇게 주차시킬 수 있는가? 그러한 숙련된 운전사도 실수할 때가 있다. 그것이 heuristic 이다.

 ......

알 고리즘 (Algorithm) 과는 달리 heuristic 은 해결책의 발견을 보장하지 않는다. 그러나 heuristic 은 알고리즘보다 효율적이다. 왜냐하면 많은 쓸모없는 대안책들을 실제 시도하지 않고도 배제시킬 수 있기 때문이다. 순회외판원 문제 (Traveling Salesman Problem), 체스 (Chess) 에서처럼 알고리즘은 극도의 비효율성을 보여주어 사실상 문제해결 (Problem Solving) 이 불가능해진다.

Chess 프로그램은 현재 상급 선수수준이지만 인간과 비교했을 때는 제한된 지능 메카니즘만을 가진다. 왜냐하면 이해를 해야할 것을 많은양의 계산으로 대신하기 때문이다. 세계 챔피언을 깨기 위해서는 초당 2억개의 position 을 파악할 수 있는 능력과 믿을 만한 heuristic 을 필요로 한다. 일단 이러한 메카니즘을 더 잘 이해하면 우리는 현재의 프로그램이 하는 것보다 훨씬 더 적은 계산을 하고서도 인간수준의 프로그램을 만들 수 있을 것이다......만일 체스에서 말의 가능한 움직임을 전체 tree 구조로 개발한다면 말 위치의 전체수는 10120  이 된다. 그것은 대단히 큰 숫자로서 예를들면 우주를 탄생시킨 빅뱅이후에 단지 1026 nanosecond 만이 흘렀다는 것에서도 알 수 있다. 전체 우주에는 단지 1075 개의 원자만이 있다는 것이다. 즉 은하수는 수십억개의 태양계로 구성되고 또한 수십억개의 은하계가 모이는 그 우주의 전체의 원자의 수이다. 그러한 숫자는 체스의 말의 움직임의 수에 비하면 아무것도 아니다.

[참고]
http://www.aistudy.co.kr/heuristic/heuristic.htm
http://www.aistudy.co.kr/heuristic/heuristic_definition.htm