State Space Graphs vs Search Trees
What you'll learn: You'll understand the crucial difference between the abstract graph of all possible states and the concrete tree of paths your search algorithm actually explores.
The Core Distinction
When solving AI search problems, there are two related but distinct structures at play:
State Space Graph: This is the complete, abstract representation of every possible state your problem can reach and every transition between them. Think of it as a map of a city showing all intersections (states) and all roads (actions) connecting them. It exists conceptually whether or not you explore it.
Search Tree: This is the concrete record of paths your search algorithm actually follows as it explores from the initial state. It's like the GPS trajectory of your actual driving through the city—it records where you've been and the routes you took to get there.
Why They're Different
Here's the key: the state space graph can have cycles (you can return to the same intersection), but the search tree never does—each node represents a unique path, not just a state.
For example, if you can reach state C by going A→B→C or A→D→C, the state space graph has just one node for C. But the search tree has two separate nodes: one representing the path [A,B,C] and another for [A,D,C].
This matters because:
- The graph shows what states exist
- The tree shows what paths you've explored
- The same state can appear multiple times in the tree (as different nodes with different paths leading to it)
- Search algorithms must track visited states to avoid redundant exploration
Key Takeaway: The state space graph is the complete problem structure; the search tree is your algorithm's exploration history, where the same state can appear multiple times via different paths.