개념
상태 공간은 문제에서 발생할 수 있는 모든 상태들의 집합이다. 탐색은 이 공간 안에서 시작 상태부터 목표 상태까지 이동하는 과정이다.
구성 요소
- 상태: 문제 해결 과정에서의 한 순간 상황
- 초기 상태: 문제를 시작하는 상태
- 목표 상태: 문제 해결이 끝났다고 판단하는 도달 대상
- 연산자: 현재 상태에서 다음 상태를 만드는 동작
- 경로: 상태들이 연결된 순서
탐색 문제는 상태 집합, 연산자, 초기 상태, 목표 상태 집합의 튜플로 나타낼 수 있다.
예시
8-Puzzle에서는 타일의 배치 하나하나가 상태이다. 빈칸을 위, 아래, 왼쪽, 오른쪽으로 움직이는 것이 연산자이다. 가능한 모든 배치가 상태 공간을 이룬다.
표현
상태 공간은 트리와 그래프로 표현할 수 있다. 트리는 루트에서 자식으로 뻗어 나가는 구조이고, 그래프는 상태 간 연결 관계를 더 일반적으로 표현한다.