휴리스틱 함수

3. 휴리스틱 함수의 효과 및 설계

휴리스틱은 탐색 알고리즘의 분기 요소를 줄여 계산 효율을 높인다. 어떤 탐색 문제에서 각 노드마다 b개의 선택이 가능하고 목표 노드의 깊이가 d라면, 원시적인 탐색 알고리즘은 해를 찾기 전에 잠재적으로 b^d개의 노드를 탐색한다. 휴리스틱은 분기 요소를 b에서 더 낮은 상수 b'로 감소시켜 탐색 알고리즘의 성능을 향상시킨다.

분기 요소는 휴리스틱 기법에서 부분 순서를 정하는 데 사용될 수 있다. 탐색 트리의 노드 n이 주어졌을 때, h₁(n)이 h₂(n)보다 낮은 분기 요소를 가지면 h₁(n) < h₂(n)으로 표현할 수 있다.

탐색 트리에서 각 노드에 낮은 분기 요소를 제공하는 휴리스틱 방법은 더 효율적으로 계산할 수 있기 때문에 특정 문제 해결에 사용된다. 공통 탐색 작업에서 낮은 분기 요소를 가진 허용되는 휴리스틱을 찾는 문제는 인공지능 분야에서 광범위하게 연구되고 있다.

휴리스틱 함수 설계에는 부프로그램 해결 비용 활용, 완화된 문제 활용, 여러 휴리스틱 함수 조합 등의 기법이 사용된다. 1993년 A.E.프리에디티스(A.E.Prieditis)는 이러한 기법들을 활용하여 주어진 문제에 대한 휴리스틱 함수를 자동으로 생성하는 ABSOLVER라는 프로그램을 만들었다. (하위 섹션에서 자세한 내용이 다루어지므로 간단하게만 언급)

3. 1. 허용 가능한 휴리스틱 함수 (Admissible Heuristic Function)

3. 2. 휴리스틱 함수 설계 기법

• 부프로그램 해결 비용 활용: 전체 문제의 일부를 해결하는 비용을 휴리스틱 함수 값으로 사용한다. 예를 들어, 10-퍼즐에서 1번부터 5번 타일을 제자리로 옮기는 비용을 휴리스틱으로 사용할 수 있다. 이때, 모든 부프로그램의 정확한 해결 비용을 저장하는 패턴 데이터베이스를 활용하면 더욱 정확한 휴리스틱 값을 얻을 수 있다.
• 완화된 문제 활용: 원래 문제보다 제약 조건이 완화된 문제의 해를 휴리스틱 함수 값으로 사용한다. 예를 들어, N-퍼즐에서 각 타일을 다른 타일과 독립적으로 움직일 수 있다고 가정하면, 맨해튼 거리가 완화된 문제의 해가 된다.
• 여러 휴리스틱 함수 조합: 여러 개의 허용 가능한 휴리스틱 함수 $h\_1(n),\; h\_2(n),\; ...,\; h\_i(n)$이 있을 때, $h(n)\; =\; \backslash max\backslash \{h\_1(n),\; h\_2(n),\; ...,\; h\_i(n)\backslash \}$는 그들 모두를 지배하는 허용 가능한 휴리스틱 함수가 된다.

4. 휴리스틱 탐색의 예시: N-퍼즐

N 퍼즐은 휴리스틱 탐색의 효과를 보여주는 대표적인 예시이다. 이 문제에서 사용되는 휴리스틱 기법은 잘못 배치된 타일의 수를 세는 것과, 각 블록의 현재 위치와 목표 위치 사이의 맨해튼 거리의 합을 구하는 것이 있다. 두 가지 모두 용인되는 방법이다.

5. 휴리스틱 탐색 알고리즘 자동 생성

1993년 A.E.프리에디티스(A.E.Prieditis)는 주어진 문제에 대한 휴리스틱 함수를 자동으로 생성하는 ABSOLVER라는 프로그램을 만들었다.

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