6. State Space Search (상태 공간 탐색)
상태 공간 탐색은 문제를 푸는 방식으로, 흔히들 FSM (Final State Machine) 이라 부르는 것과 많이 닮아있다. 그래프는 상태를 나타내는 노드와, 이 노드를 연결하는 선으로 구성되어 있다. 각 노드들은 어떤 상태에 있는지를 표현하고, 이 노드와 노드를 연결하는 선은 상태가 어떻게 변할 수 있는지를 나타낸다.
Figure 1. Konigsberg Bridge System
위의 그림은 아주 유명한 코닉스버그 의 다리 이다. 짝수개의 연결선을 가진 노드는 짝수개가 있어야하고, 홀수개를 가진 노드는 홀수개가 있어야지만, '지나 갔던 길을 다시 지나지 않고 모든길을 지날 수 있다' 라는 명제가 성립한다는 문제이다. 사실 노드와 선을 연결하는 그래프라고 하면, 우리에게는 트리 형태의 구조가 조금더 익숙하다.
Figure 2. Tree Example
트리 구조에서 보면, a는 b의 'Parent'이다. 이처럼 직렬로 연결되어 있는 바로 위의 노드를 'Parent'라고 한다. 그리고, b는 a의 'chile'라고 할 수 있다. 그리고 d와 a처럼, 직렬로 연결되어 있지는 않지만 원류에 위치하는 것을 'ancestor'라고 하는데 rooted node는 모든 노드의 'ancestor' 이다. 위 트리구조의 rooted node는 a 이다.
이처럼 각 상태를 나타내는 노드로 나타내었다면, State Space Search는 goal로 향하는 최단 거리의 path root(경로) 를 찾으면 된다. 각 트리의 가장 아랫부분이 도달 할 수 있는 결과라면, State Space Search는 그 결과들중에 자신이 원하는 goal state가 있는지 검색 해야 할 것이다. 이때에 사용 할 수 있는 방법이 (트리의 경우에) Breadth-First Search가 있고, Depth-First Search가 있다. 전자의 경우엔 a b c d e f g 의 순서로 각 노드를 검사하고, 후자의 경우엔 a b d g e c f의 순서로 탐색을 한다.
breadth-first search의 경우엔 최단 거리를 찾아 낼 수 있다는 장점이 있지만, bad branching factor가 존재한다면, goal node를 찾는 것을 방해 할 수 있다. 반면에 Depth-First Search는 수많은 모든 스테이트들을 고려하는데에 시간을 낭비하지 않고 goal node로 가는 길을 찾는다. 하지만, 최단거리를 찾지 못 할 수 있고, 그래프의 한쪽으로 너무 깊게 빠져들어 갈 수 있다는 단점이 있다.