허용적 휴리스틱

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

탐색 알고리즘

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

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

$f(n)=g(n)+h(n)$

$f(n)$: 평가함수

$g(n)$: 출발 꼭지점부터 현재 꼭지점까지의 비용

$h(n)$: 현재 꼭지점에서 목표 꼭지점까지의 추정 비용

$h(n)$는 휴리스틱 함수로 평가된다. A* 알고리즘을 비 허용적 휴리스틱 함수를 이용해 사용하면 $f(n)$을 과평가하는 바람에 최적해를 발견하지 못하고 지나칠 수 있다.