허용적 휴리스틱 문서 원본 보기

{{위키데이터 속성 추적}}
[[컴퓨터 과학]]에서 [[길 찾기]] [[알고리즘]]에서 [[휴리스틱 함수]]가 목표에 도달하는 데 필요한 비용을 전혀 과평가 하지 않는 경우, 이 함수를 '''허용적 휴리스틱''' 함수라고 부른다. 허용적 휴리스틱 함수는 어떤 지점에서도 항상 최적의 길찾기 비용보다 낮은 비용을 추정해야 한다.

== 탐색 알고리즘 ==
허용적 휴리스틱은 [[탐색 알고리즘]]에서 목표에 도달하는 비용을 추정하는데 쓰인다.
휴리스틱 함수가 항상 실제값보다 작거나 같은 값만을 가리킨다면 휴리스틱 함수는 허용적이다.
탐색 알고리즘은 현재의 꼭지점에서 목표 꼭지점까지의 비용을 추정할 때 휴리스틱을 사용한다.

예를 들어, 현재의 꼭지점 <math>n</math>에 대한 [[A* 알고리즘]]의 평가함수는 다음과 같다.

<math>f(n) = g(n) + h(n)</math>

:<math>f(n)</math>: 평가함수
:<math>g(n)</math>: 출발 꼭지점부터 현재 꼭지점까지의 비용
:<math>h(n)</math>: 현재 꼭지점에서 목표 꼭지점까지의 추정 비용

<math>h(n)</math>는 휴리스틱 함수로 평가된다.
A* 알고리즘을 비 허용적 휴리스틱 함수를 이용해 사용하면 <math>f(n)</math>을 과평가하는 바람에 최적해를 발견하지 못하고 지나칠 수 있다.
== 같이 보기 ==
* [[휴리스틱 함수]]
* [[검색 알고리즘]]

{{전거 통제}}

[[분류:인공지능]]
[[분류:검색 알고리즘]]