휴리스틱 탐색 및 A* 알고리즘

휴리스틱 탐색은 목표까지 남은 비용에 대한 문제별 추정치를 사용하여 어떤 상태를 먼저 탐색할지 안내합니다. A*는 이의 대표적인 알고리즘으로, 현재까지의 비용과 남은 비용 추정치의 합계 순서로 상태를 확장합니다.

Definition

휴리스틱 탐색은 시작점으로부터 알려진 비용과 남은 비용에 대한 휴리스틱 추정치를 결합한 평가 함수를 사용하여 프론티어의 순서를 정하는 정보 기반 탐색입니다. A*는 f(n) = g(n) + h(n)을 사용하며, h가 허용 가능할 때 최적입니다.

Scope

이 주제는 최우선 탐색(best-first search)과 A* 알고리즘을 중심으로 하는 정보 기반(휴리스틱) 탐색 전략을 다룹니다. 여기에는 휴리스틱 함수의 설계 및 속성(허용성, 일관성/단조성), 이러한 속성이 부여하는 최적성 및 효율성 보장, 그리고 반복 심화 A* (IDA*)와 같은 메모리 제한 변형이 포함됩니다. 휴리스틱이 어떻게 구성되는지(완화된 문제, 패턴 데이터베이스)와 정확성 및 계산 간의 균형을 어떻게 맞추는지도 다룹니다. 데이터로부터 휴리스틱을 학습하는 것은 기계 학습 하위 분야에 속합니다.

Core questions

• 휴리스틱을 허용 가능하게 만드는 요인은 무엇이며, 허용성이 A* 최적성을 보장하는 이유는 무엇입니까?
• 일관성(단조성)은 어떻게 보장을 강화하고 노드 재확장을 방지합니까?
• 예를 들어, 문제의 완화된 버전으로부터 좋은 휴리스틱은 어떻게 설계됩니까?
• IDA*와 같은 메모리 제한 변형은 제한된 공간에서 어떻게 최적성을 유지합니까?

Key concepts

• 평가 함수 f = g + h
• 허용 가능한 휴리스틱
• 일관된 (단조) 휴리스틱
• 탐욕적 최우선 탐색
• A* 탐색
• 반복 심화 A* (IDA*)
• 휴리스틱 우위
• 완화된 문제 및 패턴 데이터베이스

Key theories

허용 가능한 휴리스틱 하에서의 A* 최적성

휴리스틱 h가 실제 남은 비용을 절대 과대평가하지 않을 때, A*는 f = g + h를 증가시키는 순서로 노드를 확장하며, 최소 비용 경로를 반환하는 것이 보장됩니다. 동일한 휴리스틱 정보를 사용하는 알고리즘 중에서 A*는 최적으로 효율적입니다.

완화를 통한 휴리스틱 설계

허용 가능한 휴리스틱은 문제의 완화된 버전(행동에 대한 제약이 적은 버전)을 해결함으로써 체계적으로 도출될 수 있습니다. 더 쉬운 문제의 정확한 비용은 원래 문제의 하한선이 되기 때문입니다. 우세한(더 많은 정보를 가진) 휴리스틱은 더 적은 노드를 확장합니다.

메모리 제한 휴리스틱 탐색

반복 심화 A*는 증가하는 f-비용 임계값으로 제한된 연속적인 깊이 우선 탐색을 수행하여, 솔루션 깊이에 비례하는 메모리로 A*와 유사한 최적성을 달성합니다.

Clinical relevance

휴리스틱 탐색은 지도 및 게임에서의 경로 찾기, 로봇 공학에서의 동작 계획, 자동화된 플래너 및 퍼즐 해결기 내부의 탐색 엔진에 활용됩니다. 휴리스틱 설계의 실질적인 기술은 대규모 문제를 허용 가능한 시간 내에 해결할 수 있는지 여부를 직접적으로 결정합니다.

History

A* 알고리즘은 Hart, Nilsson, Raphael (1968)에 의해 소개되었으며, 휴리스틱 탐색에 공식적인 최적성 기반을 제공했습니다. Pearl의 1984년 저서 'Heuristics'는 결정적인 이론적 처리를 제공했으며, Korf의 1985년 IDA*는 A*의 메모리 비용 문제를 해결했습니다. 이러한 결과는 AI 교육의 핵심 자료로 남아 있습니다.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

허용 가능한 휴리스틱이란 무엇입니까?

휴리스틱은 어떤 상태에서든 목표에 도달하는 실제 비용을 절대 과대평가하지 않으면 허용 가능합니다. 허용성은 A*가 최적(최소 비용) 솔루션을 찾는 것이 보장되는 조건입니다.

탐욕적 최우선 탐색과 A*의 차이점은 무엇입니까?

탐욕적 최우선 탐색은 휴리스틱(h)만을 사용하여 목표에 가장 가깝게 보이는 상태를 확장합니다. 이는 빠르지만 최적과는 거리가 멀 수 있습니다. A*는 지금까지 발생한 실제 비용(g)을 추가하여 f = g + h에 따라 확장하며, 휴리스틱이 허용 가능할 때 최적성을 유지합니다.