인정적 휴리스틱

컴퓨터 과학에서, 특히 경로 탐색과 관련된 알고리즘에서는, 목표 도달에 드는 비용을 결코 과대평가하지 않는 경우, 즉 목표에 도달하기 위해 추정하는 비용이 경로의 현재 지점에서 가능한 최저 비용보다 높지 않은 경우, 휴리스틱 함수가 인정된다고 한다.^[1]

검색 알고리즘

인정된 경험적 경험적 발견은 정보에 입각한 검색 알고리즘에서 목표 상태에 도달하는 비용을 추정하는 데 사용된다. 경험적 발견이 검색 문제에 대해 허용되려면, 추정 비용은 항상 목표 상태에 도달하는 실제 비용보다 낮거나 같아야 한다. 검색 알고리즘은 허용 가능한 경험적 접근법을 사용하여 현재 노드에서 목표 상태에 대한 추정 최적 경로를 찾는다. 예를 들어 A* 검색에서 평가 기능(여기서 n ${\displaystyle$ n$}$이(가$$) 현재 노드임)은 다음과 같다.

${\displaystyle f(n)=g(n)+h(n)}$

어디에

${\displaystyle f}$( ${\displaystyle n}$) ${\displaystyle f(n)}$ $$= 평가 함수.

${\displaystyle g}$( ${\displaystyle n}$) ${\displaystyle g(n)}$ $$= 시작 노드에서 현재 노드까지의 비용

${\displaystyle h}$( ${\displaystyle n}$) ${\displaystyle h(n)}$ $$= 현재 노드에서 목표까지의 추정 비용.

${\displaystyle h}$( ${\displaystyle n}$) ${\displaystyle h(n)}$은(는) 휴리스틱 함수를 사용하여$$ 계산한다. 비적용 휴리스틱을 사용하는 경우, $A{\displaystyle }$* 알고리즘은 f${\displaystyle }$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle f(n)}$의 과대평가로 인해 검색 문제에 대한 최적의 해결책을 간과할 수 있다$.$

공식화

${\displaystyle n}$ $[\displaystyle n}$은(는) 노드임

${\displaystyle h}$ $[\displaystyle h}$은(는) 휴리스틱이다.

${\displaystyle h}$( ${\displaystyle n}$) ${\displaystyle h(n)}$은(는) $n{\displaystyle }$ ${\$$displaystyle$ $h$$}$에서 목표에 도달하기 위해 h ${\$$displaystyle$h}로 표시된 비용이다$$.

${\displaystyle h^{}}$ ${\displaystyle {\ast }^{}}$(${\displaystyle n}$) ${\displaystyle h^{*}(n)}$은(는) $n{\displaystyle }$ ${\displaystyle$ n$}$에서 목표에 도달하기 위한 최적의 비용이다$$.

${\displaystyle }$${\displaystyle h}$${\displaystyle }$( ${\displaystyle n}$) ${\displaystyle h(n)}$이(가) 허용되는$$ 경우, $\forall {\displaystyle \mathrm{}}$ n ${\displaystyle \forall n}$

${\displaystyle h(n)\leq h^{*}(n)}$

건설

허용 가능한 경험적 경험적 경험은 문제의 완화된 버전 또는 문제의 하위 문제에 대한 정확한 해결책을 저장하는 패턴 데이터베이스의 정보 또는 귀납적 학습 방법을 사용하여 얻을 수 있다.

예

허용 가능한 경험적 접근성의 두 가지 다른 예가 15개의 퍼즐 문제에 적용된다.

• 해밍 거리
• 맨해튼 거리

해밍 거리는 잘못 배치된 총 타일 수입니다. 타일을 올바르게 정렬하기 위한 총 이동 횟수가 잘못 배치된 타일의 수(각 타일은 적어도 한 번 이상 이동해야 함)이기 때문에 이러한 경험적 발견이 허용된다는 것은 분명하다. 골(주문된 퍼즐)까지의 비용(이동 횟수)은 적어도 퍼즐의 해밍 거리(Hamming distance)이다.

퍼즐의 맨해튼 거리는 다음과 같이 정의된다.

${\displaystyle h(n)=\sum _{\text{all tiles}{\mathit{distance}}({\text{direction, 올바른 위치})}}$

플레이어가 숫자를 정렬할 수 있도록 각 타일을 이동하려는 아래의 퍼즐을 고려하십시오. 맨해튼 거리는 모든 타일이 적어도 그 사이와 그 정확한 위치 사이에 있는 점의 수만큼 이동해야 하기 때문에 이 경우 허용 가능한 경험적 휴리스틱이다.[2]

43	61	30	81
72	123	93	144
153	132	14	54
24	101	111

첨자는 각 타일의 맨해튼 거리를 보여준다. 제시된 퍼즐의 맨해튼의 총 거리는 다음과 같다.

${\displaystyle h(n)=3+1+0+1+2+3+3+3+3+3+3+2+4+4+4+1+1+1=36}$

최적성 증명

반복적으로 여러 후보 경로의 최저 평가 경로(현재 비용 + 휴리스틱)만 진행하는 알고리즘에서 허용 가능한 경험적 접근법을 사용하는 경우, 탐색이 목표에 도달하는 순간 종료하고 결정적으로 모든 최적 경로를 종료하기 전에 닫지 않는다(A* 검색 알고리즘으로 가능한 경우). 이 알고리즘은 최적의^[3] 경로에서만 종료할 수 있다. 그 이유를 알아보려면 모순에 의한 다음과 같은 증거를 고려하십시오.

그러한 알고리즘이 실제 비용 S의_true 최적 경로 S보다 큰 실제 비용 T의_true 경로 T에서 가까스로 종료되었다고 가정한다. 즉, 종료하기 전에 T의 평가된 원가가 S의 평가된 원가보다 작거나 같았음을 의미한다(아니면 S를 선택했을 것이다). 이러한 평가된 비용 T와_eval S를_eval 각각 나타낸다. 위 내용은 다음과 같이 요약할 수 있다.

S_true < T_true

T_eval ≤ S_eval

만일 우리의 경험적 경험적 발견이 허용된다면, 이 Penultimate 단계 T_eval = T에서_true 경험적 발견에 의한 실제 비용 증가는 허용되지 않을 것이고 경험적 발견은 부정적일 수 없기 때문이다. 반면에, 인정된 경험적 경험적 경험은 위의 불평등과 결합된_eval S s_true S가 우리에게_eval T < T_true 그리고 더 구체적으로_eval T t_true T를 줄 것을 요구한다. T와_evaltrue T는 같을 수 없고 불평등할 수 없기 때문에 우리의 가정은 거짓이어야 하며 따라서 최적의 경로보다 더 비용이 많이 드는 경로에서 종결되는 것은 불가능해야 한다.

예를 들어,^[4] 다음과 같이 비용이 발생한다고 합시다: (노드의 위/아래 비용은 경험적 경험적 경험이며, 가장자리에 있는 비용은 실제 비용)

 0 10 0 100 0 START ---- O ---- 골 0 100 O ------ O -------- O 100 1 100 

따라서 예상 총비용($예{\displaystyle }$: f${\displaystyle }$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle f(n)}$이$($가) ${\displaystyle 10}$+ ${\displaystyle 0}$= ${\displaystyle 10}$ ${\displaystyle 10+0=10}$이므로, 우리는 상단 중간 노드를 방문하기 시작할 것이다$.$ 그런 다음 목표는 ${\displaystyle \mathrm{후보}}$일 것이며$,$ $f{\displaystyle }$(${\displaystyle \mathrm{n}}$) {\$displaystyle f(n)}$은$($는) 10 + 100 +${\displaystyle 0}$= ${\displaystyle 110}$ {\$displaystyle$ 10+100+0$=110$ 그런 다음 아래 노드를 차례로 선택한 다음 업데이트된 목표가 뒤따라야 하는데, 이들 노드는 모두 $현재{\displaystyle }$ 목표의$$ $f{\displaystyle (n)}$ ${\displaystyle f(n)}$보다 f${\displaystyle (}$${\displaystyle n}$) {\displaystyle f$(n$)}이$$(n$)$보다 $낮기{\displaystyle }$ 때문이다. 즉,${\displaystyle \mathrm{그들}}$의 f$(n$) {\$displaystyle$ f($n$)는 ${\displaystyle 100}$, 101$,$ ${\displaystyle 102,}$ 102, 102$,102$,102,$102$,102,102, 102$.$ 그래서 목표가 후보임에도 불구하고 아직 더 좋은 길이 남아 있기 때문에 뽑을 수 없었다. 이런 식으로, 인정된 경험적 휴리시즘은 최적성을 보장할 수 있다.

그러나 허용 가능한 경험적 휴리스틱이 최종 최적성을 보장할 수 있지만 반드시 효율적인 것은 아니라는 점에 유의한다.

메모들

모든 일관된 휴리스틱스는 인정되지만, 모든 허용 휴리스틱스는 인정되지 않는다.

트리 검색 문제의 경우 허용 가능한 경험적 접근법을 사용할 경우 A* 검색 알고리즘은 하위 최적 목표 노드를 반환하지 않는다.

참조

참고 항목

• 일관된 휴리스틱
• 휴리스틱 함수
• 검색 알고리즘