휴리스틱 함수 문서 원본 보기

{{위키데이터 속성 추적}}
{{출처 필요|날짜=2010-9-17}}
'''휴리스틱 함수'''(heuristic function)는 가용한 정보를 기반으로 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 [[탐색 알고리즘]]의 대안 [[함수]]이다.

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

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

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

=== 계산 성능 측면에서 휴리스틱 함수의 효과 ===

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

분기요소는 휴리스틱 기법에서 [[부분 순서]]를 정기하는 데에 사용할 수 있다. 즉 탐색 트리의 노드 <math>n</math>이 주어질 때, <math>h_1(n)</math>이 <math>h_2(n)</math>보다 낮은 분기요소를 가지면, <math>h_1(n) < h_2(n)</math>로 표현할 수 있다.

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

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

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

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

* 용인된 휴리스틱 함수들 <math>h_1(n), h_2(n), ..., h_i(n)</math>의 집합이 주어졌을 때, 함수 <math>h(n) = \max\{h_1(n), h_2(n), ..., h_i(n)\}</math>는 그들 모두를 지배하는 용인된 휴리스틱 함수이다.

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

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



== 같이 보기 ==
* [[휴리스틱 이론]]
* [[인공 지능]]
* [[일관된 휴리스틱]]
* [[전문가 시스템]]
* [[휴리스틱 평가]]
* [[추론 엔진]]
* [[질의]]
* [[문제 풀이]]

[[분류:인공지능]]
[[분류:함수와 사상]]