휴리스틱 알고리즘 (Heuristic)

휴리스틱 알고리즘 (Heuristic)

 

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

 명의라고 소문난 대부분의 의사가 진단을 할 때 몇가지 핵심되는 내용에 대한 문진과 병리 자료로서 진단을 한다. 그리고 대부분 정확하다. 그가 진단할 때 매번 의학도 시절부터 배운 엄청난 양의 지식을 되새기지 않아도 그는 그동안의 진료 경험으로 진단을 수행한다.

 그러나 간혹 조기 진단해야 할 암을 발견해 내지 못해 곤란을 겪기도 한다. 초보 운전자가 가장 어려움을 겪는 것은 좁은 주차장에서의 주차이다. 숙련된 운전사는 놀라우리 만한 감각으로 정확하게 주차시킨다. 무인 자동차가 그렇게 주차시킬 수 있는가? 그러한 숙련된 운전사도 실수할 때가 있다. 그것이 heuristic 이다.

 

 

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

 

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