휴리스틱이 허용되는 것으로 간주된다는 것은 무엇을 의미합니까?

Question

검색 알고리즘에 대한 허용 가능한 휴리스틱은 결코 목표에 대한 최단 경로를 과대 평가하지 않는다고 들었습니다. 그러나 비 목표 국가 노드가 0의 경험적 가치를 갖는 것이 유효한가 아니면 목표 상태 만이 경험적 가치를 가질 수 있다고 말하는 추가 허용 규칙인가?

A = 5 
B = 4 
C = 3 
D = 0 

는 다음 휴리스틱 유효 같다 : 다음과 같이

는 예를 들어, 노드 및 목표 상태 D 사이의 최단 경로는

A = 4 
B = 4 
C = 0 
D = 0 

이 발견은 유효한 것인가 (반면 또한 쓸모없는 것임)

A = 0 
B = 0 
C = 0 
D = 0 

Answer 1

허용 가능한 휴리스틱은 단순히, 당신이 말했듯이, 과대 평가 목표까지의 거리. 은을 과소 평가해서 허용 한 두 가지 예는 참으로 유효한 인정 가능한 발견법입니다.

일반적으로 우리가 이러한 휴리스틱 스 (예 : A *)에 대해 말하는 알고리즘의 종류에서 발견 적 방법이 가능한 한 진리에 가깝다면 이점이 있습니다. 그래서, 당신이 이미 알아 차렸 듯이, 모든 노드에 대한 경험적 가치가 0 인 마지막 예제는 그리 유용하지 않을 것입니다. 일반적으로 허용 가능한 상태에서 가능한 한 진실에 가까운 휴리스틱 값을 원합니다 (결코을 과대 평가)