A* 알고리즘의 정확한 공식화

Question

A* Path-Finding 알고리즘의 정의를보고 있으며 다른 위치에서 다소 다르게 정의되는 것 같습니다.

차이점은 노드의 후계자를 통과 할 때 수행되고 후계자가 닫힌 목록에 있음을 찾을 때 수행됩니다.

• 하나의 접근법 (제안 위키 백과, 그리고 이 기사) 말한다 : 후임자가 닫힌 목록에 있다면, 그냥 무시하십시오
• 또 다른 접근법 (제안 여기 그리고 여기, 예를 들어) 말한다 : 후임자가 폐쇄 된 목록에 있으면 비용을 조사하십시오. 현재 계산 된 점수보다 높으면 향후 시험을 위해 폐쇄 목록에서 항목을 제거하십시오.

혼란 스러워요 - 어떤 방법이 맞습니까? 직관적으로, 첫 번째는 나에게 더 의미가 있지만, 나는 정의의 차이에 대해 궁금합니다. 정의 중 하나가 잘못 되었습니까, 아니면 어떻게 든 동형입니까?

Answer 1

첫 번째 접근법은 반복 된 상태로의 최적 경로가 항상 가장 먼저 따라야하는 경우에만 최적입니다. 휴리스틱 기능에 속성이있는 경우이 속성은 일관성 (또한 호출 수도원). 휴리스틱 기능은 모든 노드에 대해 일관성이 있습니다. n 그리고 모든 후계자 n' 의 n, 목표에 도달하는 예상 비용 n 도착하는 단계 비용보다 크지 않습니다. n' ~에서 n 또한 목표에 도달하는 예상 비용 n.

두 번째 접근법은 휴리스틱 기능을 인정할 수있는 경우, 즉 목표에 도달하는 데 드는 비용을 과대 평가하지 않는다면 최적입니다.

모든 일관된 휴리스틱 기능도 인정할 수 있습니다. 일관성은 허용보다 엄격한 요구 사항이지만, 허용하지만 일관되지 않은 휴리스틱 기능을 조정하기 위해 매우 열심히 노력해야합니다.

따라서, 두 번째 접근법은 휴리스틱 함수의 엄격하게 더 큰 하위 집합에서 작동하기 때문에 더 일반적이지만, 첫 번째 접근법은 일반적으로 실제로 충분합니다.

참조 : 하위 섹션 A* 검색 : 총 추정 솔루션 비용 최소화 섹션에서 4.1 정보 (휴리스틱) 검색 전략 책의 인공 지능 : 현대적인 접근.