휴리스틱 함수

이 문서의 내용은 출처가 분명하지 않습니다. 이 문서를 편집하여, 신뢰할 수 있는 출처를 표기해 주세요. 검증되지 않은 내용은 삭제될 수도 있습니다. 내용에 대한 의견은 토론 문서에서 나누어 주세요. (2010년 9월)

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

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

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

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

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

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

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

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

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

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

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

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

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

• 휴리스틱 이론
• 인공 지능
• 일관된 휴리스틱
• 전문가 시스템
• 휴리스틱 평가
• 추론 엔진
• 질의
• 문제 풀이