State Space Graphs vs. Search Trees

State Space Graphs

---

• 그래프는 state들을 추상화 한 것이다.
• 그래프에서 각 state는 한 번만 발생한다. (Search Trees와의 차이점)
• 보통은 전체 그래프를 메모리에 구축하기 힘들다.(너무 크기 때문) 하지만 유용하게 써먹을 수 있다.

Search Trees

---

• 루트노드는 Start state이다.
• 대부분의 문제에 대해 전체 트리를 구축하기 힘들다

State Space Graphs vs. Search Trees

---

• Search Tree의 각 노드는 State Space Graph의 전체 Path다.
• 필요에 따라 둘 다 구성하고 가능한 작게 구성하는 것이 좋다.

좌측 그래프를 트리로 구현한다면? (S노드가 Start state, G노드가 Goal state)

그래프에서 사이클이 존재하기때문에 단순 tree로 구현한다면 우측과 같이 tree depth를 무한으로 확장해 나갈 것이다.