상태 공간 탐색

상태 공간 탐색(state-space search)은 인공지능(AI)을 포함한 컴퓨터 과학 분야에서 원하는 속성을 가진 목표 상태를 찾기 위해 인스턴스의 연속적인 구성 또는 상태를 고려하는 과정이다.

문제는 종종 문제가 있을 수 있는 상태의 집합인 상태 공간으로 모델링된다. 상태 집합은 첫 번째 상태를 두 번째 상태로 변환하는 작업을 수행할 수 있는 경우 두 상태가 연결된 그래프를 형성한다.

상태 공간 탐색은 전통적인 컴퓨터 과학 검색 방법과 종종 다르다. 왜냐하면 상태 공간은 암묵적이기 때문이다. 즉, 일반적인 상태 공간 그래프는 생성하여 메모리에 저장하기에는 너무 크다. 대신, 노드는 탐색될 때 생성되고 일반적으로 그 후에는 폐기된다. 조합 탐색 인스턴스에 대한 해결책은 목표 상태 자체이거나 일부 초기 상태에서 목표 상태로 가는 경로로 구성될 수 있다.

표현
상태 공간 탐색에서 상태 공간은 공식적으로  튜플로 표현되며, 여기서:
는 가능한 모든 상태의 집합이다.
는 특정 상태와 관련 없이 전체 상태 공간에 대한 가능한 행동 집합이다.
는 특정 상태에서 어떤 행동을 수행할 수 있는지 설정하는 함수이다.
는 상태 에서 행동 를 수행하여 도달한 상태를 반환하는 함수이다.
는 상태 에서 행동 를 수행하는 비용이다. 많은 상태 공간에서 는 상수이지만 항상 그런 것은 아니다.

상태 공간 탐색 알고리즘의 예시
정보 없는 탐색
풀(Poole)과 맥워스(Mackworth)에 따르면 다음은 목표의 위치에 대한 사전 정보가 없는 정보 없는 상태 공간 탐색 방법이다.
 전통적인 깊이 우선 탐색
 너비 우선 탐색
 반복적 깊이심화 탐색
 최저 비용 우선 탐색 / 균일 비용 탐색 (UCS)

정보 있는 탐색
이 방법은 휴리스틱 함수의 형태로 목표 위치를 사용한다. 풀과 맥워스는 다음 예시들을 정보 있는 탐색 알고리즘으로 언급한다.
 정보/휴리스틱 깊이 우선 탐색
 탐욕적 최상 우선 탐색
 A* 검색

 같이 보기 
 상태 공간
 분기 한정법 – 상태 공간 탐색의 부분 집합을 가지치기하여 효율성을 높이는 방법

 각주 

 Stuart J. Russell and Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.

분류:검색 알고리즘