휴리스틱과 메타휴리스틱

일반적으로 우리가 연습하는, 온라인 저지 시스템에 제출하는 프로그램은 특정 문제에 대해서 언제나 같은 정확한 결과가 나오는 결정론적 알고리즘이다. 하지만 사람의 문제해결을 생각해보면, 어떤 문제의 탐색 범위가 너무 넓거나 너무 복잡한 연산을 요구한다면 특정 범위를 뛰어넘거나 직관을 사용하는 기법을 사용하기도 한다.

예를 들어 내가 체스를 둔다고 생각을 해보면, 모든 기물에 대해 이동할 수 있는 모든 경우를 고려하지도 않을 뿐더러, 각 경우에 대해 얼마나 좋은 결과가 나오는 지를 정확히 계산하지도 못한다. 하지만 내가 마음속으로 움직일 기물을 몇 개 정해놓고 그 기물로 어떤 위치에 이동했을 때 상대의 기물을 아무 리스크 없이 제거할 수 있거나, 그 움직임을 통해 나중에 상대의 말을 손해 없이 잡을 수 있는 상황을 만들 수 있다는 판단이 서면 이를 행한다. 그게 최적의 수인지 알 수 없고, 상대의 움직임에 의해 더 안좋은 상황으로 변할 수도 있다. 하지만 그 모든 것을 고려할 여력이 안되기 때문에 이와 같은 전략을 사용하게 된다.

A heuristic or heuristic technique (/hjʊəˈrɪstɪk/; Ancient Greek: εὑρίσκω, heurískō, ‘I find, discover’) is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, short-term goal or approximation. - Wikipedia

이렇게 문제를 해결하는 방법을 휴리스틱이라고 한다. 컴퓨터를 이용한 문제 해결에 대해서도 휴리스틱이 적용될 수 있다. 결정론적 알고리즘을 세워서 완벽하게 문제를 풀기에는 탐색 공간이 너무 넓거나, 시간이나 메모리가 부족한 문제에 대해서 특히 그렇다. NP-완전이라고 알려진 배낭 문제(knapsack problem), 외판원 문제(traveling salesman problem) 등에 대해 충분히 만족할 만한 근사해를 찾기 위해 휴리스틱을 적용할 수 있다. 결정론적 알고리즘 중 탐욕법이 있는데, 이 또한 휴리스틱으로 생각할 수 있다. 문제를 직관에 의해 탐욕적으로 해결하려는 시도를 하는 휴리스틱이고, 정말로 그게 문제에 대해 최적의 해를 제공할 뿐이다.

휴리스틱으로 문제를 해결할 때 직접 그 문제의 특성을 이용해서 알고리즘을 설계할 수도 있지만, 휴리스틱을 일반적으로 만들어내는 메타휴리스틱 알고리즘도 존재한다. 대부분의 문제는 아주 큰 탐색 공간에 대해 특정 함수의 값을 최소로 만드는 해를 찾는 최적화 문제로 변환될 수 있다. 이 때, 임의의 초기값을 잡고 그 함수가 낮아지는 쪽으로 계속 이동하는 간단한 전략도 hill climbing method라는 이름을 가진 메타휴리스틱 알고리즘이다.