State Space Tree   상태 공간 트리

1. 상태 공간 트리 (State Space Tree)

  ㅇ 문제 해결 과정 중 각각의 상태를 하나의 노드로써 나타낸 트리
     - 문제의 해를 만들어 가는 공간을 트리 형태로 나타내거나,
     - 해들을 나타낸 트리 공간에서 적절한 해를 탐색하게 됨

  ㅇ 상태로써 노드의 표현
     - 루트 노드 : 출발점
     - 내부 노드 : 부분 후보 해
        . 문제 풀이 과정 중의 진행 상태
     - 리프 노드 : 후보 해
        . 결국, 가능한 모든 후보 해들을 리프 노드로써 갖게됨
     - 루트 노드 ~ 리프 노드 경로 : 하나의 후보 해를 만들어가는 과정

  ㅇ 해들의 공간에서, 적절한 해를 탐색하는 알고리즘 例)
     - 백트래킹, 한정분기법, A* 알고리즘 등