휴리스틱 함수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

휴리스틱 함수(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-퍼즐을 대해, 기존의 다른 휴리스틱 해법보다 우수한 새로운 해법을 만들어냈으며, 루빅스 큐브에 대한 유용한 휴리스틱 해법을 최초로 발견하였다..

같이 보기[편집]