[인공지능/Artificial Intelligence] 상태공간과 탐색 | 맹목적 탐색 기법 | 휴리스틱 탐색 기법

상태공간과 탐색

 - 탐색(search)이란 문제의 해(solution)가 될 수 있는 것들의 집합을 공간(space)으로 간주하고, 문제에 대한 최적의 해를 찾기 위해 공간을 체계적으로 찾아보는 것이다. 해(solution)는 일련의 동작으로 구성되거나 하나의 상태로 구성된다. 탐색의 예로는 선교사-식인종 강건너기 문제, 틱-택-토, 8-퍼즐 문제, 8-queen문제 등이 있다.

 

 - 상태(state)란 특정 시점에 문제의 세계가 처해있는 모습을 말한다.

 - 세계(world)란 문제에 포함된 대상들과 이들의 상황을 포괄적으로 지칭한다.

 - 상태공간(state space)이란 문제 해결 과정에서 초기 상태로부터 도달할 수 있는 모든 상태들의 집합, 또는 문제의 해가 될 가능성이 있는 모든 상태들의 집합을 말한다.

 - 상태는 초기 상태(initial state)와 목표 상태(goal state)로 나타낼 수 있는데, 초기 상태란 문제가 주어진 시점의 시작상태, 목표 상태는 문제에서 원하는 최종 상태를 말한다.

 

맹목적 탐색(blind search)

 맹목적 탐색(blind search)이란 정해진 순서에 따라 상태공간 그래프를 점진적으로 생성해 나가면서 해를 탐색하는 방법이다.

 

정보이용 탐색(informed search)

 정보이용 탐색(informed search)은 휴리스틱 탐색(heuristic search)이다. 휴리스틱이란 그리스어로 찾다, 발견하다 라는 뜻이다. 시간이나 정보가 불충분하여 합리적인 판단을 할 수 없거나, 굳이 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 어림짐작하는 것을 말한다. 요약하면, 어떤 대상에 대한 정확한 값은 아니지만, 대충 어림짐작할 때 쓸 수 있는 방법이라고 할 수 있다.