순간 상태를 공간으로 처리하는 상태 공간 탐색(State Space Search)

A.I에서 알고리즘으로 어떤 해답을 탐색한다는 것은 다른 말로 바꿔 말하자면, 문제를 해결(Problem Solving)하는 과정이라고 표현할 수 있다. 다양한 알고리즘들이 문제를 해결하는 방법을 가지고 있다. 어떤 리스트를 소팅(Sorting)해라라고 할 때 하나의 알고리즘만으로 소팅하지 않는다. 데이터의 구조 및 상황에 따라서 적절한 알고리즘을 선택하여 정렬을 수행하는데 A.I 역시 하나의 방법으로만 탐색(즉, 해답을 찾는..)을 하지는 않는다.

탐색 알고리즘 중에 상태 공간 탐색이라는 방법(혹은 알고리즘)이 있는데 이 방식은 제목에서 알다시피 상태 공간을 이용한 탐색방법이다. 상태 공간 탐색은 여러가지 대표적으로 잘 알려진 문제를 해결할 수 있는데 대표적으로 "퍼즐", "틱택토(tic-tac-toe)", "TSP(Traveling Salesperson Problem)", "강건너기(River Crossing Puzzle)" 같은 문제들이 있다. 좀 더 확장하면, 매우 작은 바둑판의 바둑같은 경우도 사실 쓰일 수 있을 것이다. 

---

상태 공간 탐색(State Space Search)

- 답을 찾아가는 과정을 상태 공간으로 보고, 이 공간들의 최적의 집합을 찾아가는 과정

상태 공간은 좀 더 쉽게 말하자면, 우리가 집을 찾아갈 때, 여러가지의 길들이 있을 것이다. 그 중에서는 가면 안되는 길도 있을테고 최적의 길도 있을 것인데 길을 선택했던 그 순간순간들을 "상태 공간(State Space)"라고 보는 것이다. 내가 현재 과정(현재의 길)에서 다른 과정(다른 길)로 넘어갔기 때문에 상태가 바뀐 것이고, 그것을 공간으로 저장을 하는 것이다.

상태 공간 탐색의 구성요소

초기 상태 혹은 시작 상태(Initial state, Start state)

- 말 그대로 이 문제를 본격적으로 다루기 전 처음의 상태이다. 네비게이션이라고 한다면, 네비게이션을 킨 그 순간의 위치가 초기상태 혹은 시작상태이다

목표 상태(goal state)

- 이 과정에서 최종적으로 원하는 상태이다. 네비게이션에서 우리가 집을 눌렀다면, 집의 위치가 바로 목표 상태이다

세계(World)

- 문제를 해결하는 모든 과정의 대상들과 상태를 포괄적으로 지칭한다 

상태 공간 탐색의 예시

가. 퍼즐 문제(숫자 퍼즐)

숫자 퍼즐은 매우 간단한 알고리즘을 배우기 좋은 놀이이다. 공간을 하나 비워놓고, 해당 공간으로 블럭들을 옮겨서 최종적으로는 원하는 숫자의 모양을 만들면 되는 게임인데 이 문제를 해결할 때 상태 공간 탐색 알고리즘을 활용한다

위와 같이 가능한 모든 집합을 생성하여, 연산을 수행하는 것이 상태 공간 탐색이다. 위 그래프를 상태 공간 그래프라고 하며, 상태 공간 그래프는 노드(상태)와 그 다음에 링크(행동)으로 연결이 된다. 

다른 예제를 살펴보도록 하자. River Crossing Puzzle이라고 하는 강 건너기 문제가 있는데 선교사 3명, 식인종 3명을 건너게 해서, 식인종이 선교사보다 많으면 잡아 먹는 규칙이 있는 것은 들어봤을 것이다. 배에는 2명까지 탑승이 가능하고, 다른쪽으로 건너야 하는 것인데 

여기서 Initial State는 강건너기 직전인 선교사 3명, 식인종 3명이고, Goal State는 강을 모두 건너게 된 선교사 3명, 식인종 3명이다. 

River Crossing Puzzle

이 모든 상황을 그래프로 표현하면

위와 같은 노드들과 링크들로 이어질 수 있다(위 그래프는 선교사 3명, 식인종 3명의 예제는 아니다)

source, http://www.aiai.ed.ac.uk/~gwickler/missionaries.html

위 이미지는 좀 더 상황을 쉽게 표현한 그래프이다. 위에서 연결되는 저 링크들의 상황을 따라가면 문제를 해결 할 수 있게 된다. 이와 같이 상태 공간 탐색은 문제를 해결하는데 매우 쉽고 간결하지만, 일반적인 문제점에 적용하기에는 메모리 공간 및 연산에 드는 Cost가 너무 많이 필요로 한다. 그래서 한번에 미리 로드하는 방식을 지양하고, 탐색과정에서 그래프를 생성하여 처리하는 방식을 주로 사용하게 된다