Back to Study Material Artificial Intelligence

State space search

State space search is a fundamental framework in AI that models problem solving as navigation through a graph of possible world states. Each node in the gr...

State space search

Representing Problems as Graphs

State space search is a fundamental framework in AI that models problem solving as navigation through a graph of possible world states. Each node in the graph represents a distinct configuration of the world, called a state. Each edge represents an action that transitions the agent from one state to another. The task is to find a path from the initial state to a goal state, possibly one that minimises cost.

The state space can be implicit, meaning it is too large to enumerate in advance, so the graph is generated on the fly as the search algorithm expands nodes. For the eight-puzzle, the complete state space contains 181,440 reachable states from any given configuration. For a chess game, the state space has approximately ten to the power of forty-seven nodes, making exhaustive exploration completely infeasible. This is why heuristics and intelligent pruning are essential for non-trivial problems.

The frontier, sometimes called the open list, contains states that have been generated but not yet expanded. The explored set, also called the closed list, tracks states already expanded to prevent revisiting them and entering infinite loops. The choice of data structure for the frontier determines which search strategy is implemented: a queue gives breadth-first search, a stack gives depth-first search, and a priority queue ordered by path cost gives uniform-cost search.

Completeness and Loops

A critical issue in state space search is loop detection. If the same state can be reached via multiple paths, a search without a closed list may revisit states infinitely. Graph search, which maintains a closed list, is complete in finite spaces where tree search may not be. Most practical implementations use graph search for this reason.

Exam Tip

A common exam task is to draw the search tree for a small problem and trace through a specified algorithm step by step. Show which node is expanded at each step, what the frontier contains after each expansion, and when the goal is first reached. For BFS, expansions proceed level by level. For DFS, they plunge as deep as possible along one branch before backtracking. Being precise about what is in the frontier at each step is what earns full marks.