휴리스틱 함수

휴리스틱 함수(heuristic function)는 가용한 정보를 기반으로 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 탐색 알고리즘의 대안 함수이다.

최단 경로[편집]

예를 들어, 최단 경로 문제에서 휴리스틱 함수 $h(n)$ 은 한 노드에서 목표 노드까지의 최소 비용 경로를 추정하는 탐색 트리의 노드들로 정의할 수 있다. 탐욕적 최우선 탐색과 A* 탐색과 같은 세련된 탐색 알고리즘에서 최선의 노드를 찾아내기 위해 휴리스틱 기법이 사용된다. 탐욕적 최우선 탐색은 휴리스틱 함수에서 최솟값을 가지는 노드를 선택할 것이다.

A* 탐색은 $g(n)+h(n)$ 가 최솟값을 가지는 노드들을 확장할 것이다. ( $g(n)$ 는 초기 상태에서 현재 노드까지의 정확한 경로 비용이며, $h(n)$ 는 목표 도달 비용을 절대 넘지 않는 용인된 함수이다.) 그러면 A*은 항상 최적의 해를 찾을 것이다.

휴리스틱과 관련된 고전적인 문제로 N 퍼즐이 있다. 이 문제에서 사용되는 휴리스틱 기법은 잘못 배치된 타일의 수를 세는 것과, 각 블록의 현재 위치와 목표 위치 사이의 맨하탄 거리(Manhattan distance)의 합을 구하는 것이 있다. 두 가지 모두 용인되는 방법이다.

계산 성능 측면에서 휴리스틱 함수의 효과[편집]

각 노드에서 선택들 $b$ , 목표 노드에서 깊이 $d$ 가 있는 어떤 탐색 문제에서, 원시적인 탐색 알고리즘은 해를 찾기 전에 노드들 $b^{d}$ 를 잠재적으로 탐색한다. 휴리스틱은 분기 기작을 이용하여 $b$ 에서 더 낮은 상수 $b'$ 로의 분기 요소를 감소시킴으로써 탐색 알고리즘의 효과를 향상시킨다.

분기요소는 휴리스틱 기법에서 부분 순서를 정기하는 데에 사용할 수 있다. 즉 탐색 트리의 노드 $n$ 이 주어질 때, $h_{1}(n)$ 이 $h_{2}(n)$ 보다 낮은 분기요소를 가지면, $h_{1}(n)<h_{2}(n)$ 로 표현할 수 있다.

탐색 트리에서 각 노드에 낮은 분기 요소를 주는 휴리스틱 방법은 좀 더 효과적으로 계산할 수 있기 때문에 특정 문제의 해상도를 위해 사용된다.

휴리스틱 탐색[편집]

공통 탐색 작업에 있어서, 낮은 분기 요소를 가진, 용인되는 휴리스틱을 찾는 문제는 인공지능 분야에서 광범위하게 조사되고 있다. 다음과 같은 몇몇 공통적인 기술들이 사용된다.

부프로그램의 해결비용은 전체 해결비용을 유용하게 예측하는 값으로 자주 사용되며, 이들은 항상 용인된다. 예를 들어, 10-퍼즐에 대한 휴리스틱은 1번~5번 타일들을 제자리로 옮기는 비용이 될 수 있다. 공통된 아이디어는 모든 부프로그램들의 경우에서 정확한 해결비용을 저장하는 패턴 데이터베이스를 사용하는 것이다.

느슨한 문제의 해는 본래 문제에서 유용한 용인된 예측을 제공하기도 한다. 예를 들어, 맨하탄 거리는 N-퍼즐의 느슨한 버전이다. 왜냐하면 각 타일을 다른 타일들과 독립적으로 움직일 수 있다고 가정하기 때문이다.

용인된 휴리스틱 함수들 $h_{1}(n),h_{2}(n),...,h_{i}(n)$ 의 집합이 주어졌을 때, 함수 $h(n)=\max\{h_{1}(n),h_{2}(n),...,h_{i}(n)\}$ 는 그들 모두를 지배하는 용인된 휴리스틱 함수이다.

1993년 A.E.프리에디티스(A.E.Prieditis)는 이런 기법들을 활용하여, 주어진 문제에 대한 휴리스틱 해법을 자동으로 생성시키는 ABOLVER라는 프로그램을 만들었다.

ABSOLVER는 8-퍼즐을 대해, 기존의 다른 휴리스틱 해법보다 우수한 새로운 해법을 만들어냈으며, 루빅스 큐브에 대한 유용한 휴리스틱 해법을 최초로 발견하였다..

같이 보기[편집]