휴리스틱 함수

1. 개요

휴리스틱 함수는 특정 상태에서 목표 상태까지의 예상 비용을 추정하는 함수로, 최단 경로 문제와 같은 탐색 문제에서 효율적인 해를 찾기 위해 사용된다. 탐욕적 최우선 탐색과 A* 탐색과 같은 알고리즘에서 최선의 노드를 선택하는 데 활용되며, N-퍼즐과 같은 문제 해결에 적용된다. 휴리스틱은 탐색 알고리즘의 분기 요소를 줄여 효율성을 높이며, 부프로그램 해결 비용, 완화된 문제, 여러 휴리스틱 함수 조합 등의 설계 기법이 사용된다. 1993년 A.E. 프리에디티스는 휴리스틱 해법을 자동 생성하는 ABOLVER 프로그램을 개발하여 8-퍼즐과 루빅스 큐브 문제에 새로운 해법을 제시했다.

2. 휴리스틱 탐색의 기본 원리

휴리스틱 탐색은 탐색 과정에서 가능한 모든 경우의 수를 탐색하는 대신, 휴리스틱 함수를 이용하여 가장 유망한 노드를 우선적으로 탐색하는 방식이다.

2.1. 휴리스틱 함수

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

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

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

2.2. A* 탐색 (A* Search)

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

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

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)

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

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

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

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 \}$는 그들 모두를 지배하는 허용 가능한 휴리스틱 함수가 된다.

1993년 A.E.프리에디티스(A.E.Prieditis)는 이러한 기법들을 활용하여 주어진 문제에 대한 휴리스틱 함수를 자동으로 생성하는 ABSOLVER라는 프로그램을 만들었다. ABSOLVER는 8-퍼즐에 대해 기존보다 우수한 휴리스틱을 찾아냈고, 루빅스 큐브에 대한 유용한 휴리스틱을 최초로 발견했다.

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

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

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

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

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