1. State-Space Search
State-space search algorithms navigate an implicitly defined graph whose nodes are states — configurations of a problem — and whose edges are actions or transitions. Unlike data-structure searching, the graph is not stored in memory; it is generated on the fly as the algorithm expands nodes.
This framework, developed in artificial intelligence 12, unifies a broad class of problems: puzzles, planning, routing, and game playing can all be cast as finding a path from an initial state \(s_0\) to a goal state \(g\) in a state-space graph.
1.1 Algorithms
| Algorithm | Searches by | Completeness | Optimal? | Paradigm |
|---|---|---|---|---|
| Uniform-Cost Search | Path cost \(g(n)\) | Yes | Yes | Uninformed |
| Greedy Best-First | Heuristic \(h(n)\) | Yes (finite) | No | Informed / Greedy |
| A* Search | \(f(n) = g(n) + h(n)\) | Yes | Yes (admissible \(h\)) | Informed / Heuristic |
| Iterative Deepening | Depth limit (DFS) | Yes | Yes (unit cost) | Uninformed |
1.2 Uninformed vs. Informed Search
Uninformed (blind) algorithms explore the state space using only structural information: which states exist, which transitions are available, and what the transition costs are. They make no assumptions about which part of the space is likely to contain the goal.
Informed algorithms additionally use a heuristic function \(h(n)\), a domain-specific estimate of the cost from state \(n\) to the nearest goal. A good heuristic dramatically reduces the number of states explored; a perfect heuristic reduces exploration to the optimal path alone.
Variables
| Symbol | Meaning |
|---|---|
| \(s_0\) | Initial state |
| \(g\) | Goal state or goal test |
| \(g(n)\) | Exact cost of the path from \(s_0\) to \(n\) found so far |
| \(h(n)\) | Heuristic estimate of cost from \(n\) to the nearest goal |
| \(h^*(n)\) | True (optimal) cost from \(n\) to the nearest goal |
| \(f(n) = g(n) + h(n)\) | Evaluation function used by A* |
| \(b\) | Branching factor — maximum number of successors of any node |
| \(d\) | Depth of the shallowest goal node |