상태 공간 탐색

상태 공간 탐색은 초기 상태에서 사용 가능한 행동을 통해 도달할 수 있는 상태들의 집합을 체계적으로 탐색하여, 목표 테스트를 만족하는 상태나 그 상태에 도달하는 경로를 찾는 과정입니다.

Definition

상태 공간 탐색은 문제를 노드가 상태이고 엣지가 행동인 그래프로 취급하며, 고정된 전략에 따라 프론티어에서 상태를 확장하여 목표 상태를 찾거나 공간이 소진될 때까지 진행합니다.

Scope

이 주제는 문제를 상태 공간(상태, 행동, 전이 모델, 목표 테스트, 경로 비용)으로 공식화하는 방법과 도메인별 지침 없이 이를 탐색하는 정보 없는 탐색 전략(너비 우선, 균일 비용, 깊이 우선, 깊이 제한, 반복 심화 탐색)을 다룹니다. 또한 이러한 전략들의 완전성, 최적성, 시간 복잡도, 공간 복잡도에 대한 분석과 반복 상태 감지를 통한 트리 탐색과 그래프 탐색의 구별을 포함합니다. 휴리스틱 지침은 휴리스틱 탐색 및 A*에 대한 별도 주제에서 다룹니다.

Core questions

• 문제는 어떻게 상태, 행동, 전이 모델, 목표 테스트로 표현되는가?
• 너비 우선, 깊이 우선, 균일 비용, 반복 심화 탐색은 프론티어 순서 지정에서 어떻게 다른가?
• 각 정보 없는 전략의 완전성, 최적성, 시간 및 공간 보장은 무엇인가?
• 그래프 탐색은 트리 탐색이 허용하는 상태의 낭비적인 재탐색을 어떻게 피하는가?

Key concepts

• 초기 상태 및 목표 테스트
• 전이 모델 및 후속 상태
• 프론티어 (열린 목록) 및 탐색된 집합
• 너비 우선 탐색
• 깊이 우선 탐색
• 균일 비용 탐색
• 반복 심화
• 트리 탐색 대 그래프 탐색

Key theories

프론티어 순서 지정이 전략을 결정한다

정보 없는 탐색 알고리즘은 프론티어에서 상태를 제거하는 순서에 의해서만 구별됩니다. FIFO 큐는 너비 우선 탐색을, LIFO 스택은 깊이 우선 탐색을, 경로 비용에 대한 우선순위 큐는 균일 비용 탐색을 제공합니다.

공간 효율적인 최적 전략으로서의 반복 심화

깊이 우선 반복 심화 탐색은 깊이 제한 깊이 우선 탐색을 증가하는 제한으로 반복적으로 실행하여, 깊이 우선 탐색의 선형 공간과 너비 우선 탐색의 완전성 및 최적성(단위 비용에서)을 결합합니다.

Clinical relevance

정보 없는 상태 공간 탐색은 경로 찾기, 퍼즐 해결, 모델 검증에서의 도달 가능성 분석, 그리고 휴리스틱 및 적대적 탐색이 구축되는 기반으로서 개념적 및 구현적 토대입니다. 그 복잡성을 이해하는 것은 맹목적 탐색이 실현 가능한 시점과 휴리스틱이 필요한 시점을 판단하는 데 도움이 됩니다.

History

체계적인 상태 공간 탐색은 1950년대의 그래프 순회 알고리즘(Moore와 Dijkstra의 최단 경로 연구 포함)에서 유래했으며, 초기 AI에서 문제 해결 모델로 구성되었습니다. Korf의 1985년 반복 심화 분석은 선형 공간을 가진 허용 가능한 트리 탐색 중에서 그 최적성을 확립했습니다.

Key figures

• Nils J. Nilsson
• Richard E. Korf
• Edward F. Moore
• Edsger W. Dijkstra

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

너비 우선 탐색은 언제 최적인가요?

너비 우선 탐색은 모든 단계의 비용이 동일할 때 최적입니다. 이는 가장 얕은 목표를 먼저 찾기 때문입니다. 단계 비용이 다를 때는 균일 비용 탐색(누적 경로 비용에 따라 프론티어를 정렬)이 가장 낮은 비용의 해를 보장하는 정보 없는 전략입니다.

단순 너비 우선 탐색 대신 반복 심화를 사용하는 이유는 무엇인가요?

너비 우선 탐색은 전체 프론티어를 저장하며 깊이에 따라 지수적인 메모리를 요구할 수 있습니다. 반복 심화는 증가하는 깊이 제한으로 깊이 우선 탐색을 반복적으로 수행하여, 얕은 노드를 재확장하는 비용을 감수하고도 단위 비용 문제에서 완전하고 최적이며 선형 메모리만 사용합니다.