State  Space

 

문제 해결 (Problem Solving) 은 다양한 문제 상태로 구성된 문제 공간 (problem space) 의 탐색 (Search) 으로 흔히 설명된다. 한 상태 (state) 는 문제의 해결 정도를 나타낸다. 문제 해결자가 처음 당면하는 상황을 초기 상태, 목표로 가고 있는 상황을 중간 상태, 그리고 목표를 목표 상태 (goal state) 라고 한다....... 여기서 문제는 문제 공간의 초기 상태에서 목표 상태에 이르기까지 일련의 가능한 조작자들을 찾는 것이다. '문제' 공간은 상태의 미로로 그리고 조작자는 상태 간을 이동하는 통로로 생각할 수 있다. 이렇게 생각하면, '해결' 은 검색 (Search), 즉 문제 해결자가 상태들의 미로에서 적절한 통로를 찾는 과정을 통해 이루어진다. 카네기 멜런대학교의 Allen NewellHerbert Simon 이 문제 해결을 상태 공간의 검색으로 보는 입장을 발전시켰고, 이 생각은 인지심리학 과 인공지능 (Artificial Intelligence) 모두에서 지배적인 문제 해결 분석이 되었다. ..... (John R. Anderson 1995)

Chimpanzee problem solving : 침팬지는 바나나를 어떻게 먹을 것인가?

실제적인 문제들의 대부분은 탐색공간이 너무 크기 때문에 명시적인 그래프로 표현할 수 없다. 이 경우에는 명시적인 (explicit) 계획 (planning) 에서 설명한 기본적인 탐색 방법에 수정이 필요하다. 첫째, 이러한 문제들은 탐색 문제로 설정하는 방법에 있어서 매우 신중해야 한다. 둘째, 방대한 탐색 그래프를 암시적으로 (implicitly) 표현하는 방법이 있어야 한다. 셋째, 이런 방대한 그래프를 탐색하기 위한 효율적인 방법이 있어야 한다...... 시작 상태로부터 행동을 취하여 도달될 수 있는 상태공간 그래프에서의 영역은 시작 상태의 정의와 각 행동들에 대한 정의에 의해 암시적으로 표현된다. 따라서 원칙적으로 암시적인 (implicit) 그래프 표현으로부터 명시적인 (explicit) 그래프를 만들어 내는 것이 가능하다 ........ 탐색 과정은 목표 노드까지의 경로가 찾아지면 종료된다. 좀 더 공식적으로 이야기하면, 상태공간 그래프의 암시적인 표현에는 세 가지 기본 요소가 있다.

크게 두 종류의 탐색 (Search) 방법이 있다. 그 중 한가지는 목표까지의 경로를 찾는 데 있어서 탐색공간의 어떤 한 부분을 다른 부분에 비해 선호할 만한 판단 근거가 없는 경우에 사용하는 방법이다. 이런 경우를 무정보 (uninformed or blind) 탐색 이라고 한다. 다른 한 가지는 탐색을 한 부분에 집중시킬 수 있도록 해주는 그 문제 고유의 정보가 있는 경우에 사용하는 방법이다. 이런 경우를 휴리스틱 (heuristic) 탐색 이라고 한다. ..... (Nils J.Nilsson 1998)

문제 공간과 검색 (Problem Space and Search) : John R. Anderson

상태공간 그래프 (State-Space Graphs)   상태공간의 설정 (Formulating the State Space) : Nils J.Nilsson