State Space Search

A state space consists of
A (possibly infinite) set of states
The start state represents the initial problem
Each state represents some configuration reachable from the start state
Some states may be goal states (solutions)
A set of operators
Applying an operator to a state transforms it to another state in the state space
Not all operators are applicable to all states
State spaces are used extensively in Artificial Intelligence (AI)
With certain modifications, any tree search technique can be applied to a graph
This includes depth-first, breadth-first, depth-first iterative deepening, and other types of searches
The difference is that a graph may have cycles
We don’t want to search around and around in a cycle
To avoid getting caught in a cycle, we must keep track of which nodes we have already explored
There are two basic techniques for this:
Keep a set of already explored nodes, or
Mark the node itself as having been explored
Marking nodes is not always possible (may not be allowed)
Here is how to do DFS on a tree:
Put the root node on a stack;while (stack is not empty) { remove a node from the stack; if (node is a goal node) return success; put all children of the node onto the stack;}return failure;
Here is how to do DFS on a graph:
Put the starting node on a stack;while (stack is not empty) { remove a node from the stack; if (node has already been visited) continue; if (node is a goal node) return success; put all adjacent nodes of the node onto the stack;}return failure;