"Many AI problems can be framed as search: describe where you start, the moves you can make, and what counts as success, then let an algorithm explore the possibilities. Search is one of the oldest ideas in AI and still sits underneath route planning, game playing, scheduling, and the reasoning steps of modern AI agents."- Claude 2026
Early AI researchers noticed that very different problems, from puzzles to route finding to proving theorems, share one shape. Describe the problem as a state space, and solving it becomes a matter of finding a path from where you are to where you want to be. This is the problem-solving agent described in Artificial Intelligence: A Modern Approach, the standard AI textbook.
- Initial state: where the agent starts
- Actions: the moves available from each state
- Transitions: where each move leads
- Goal test: how to recognize success
- Path cost: distance, time, money, or risk
- Solution: a sequence of actions that reaches the goal
Every search algorithm keeps a frontier of paths it hasn't explored yet. What separates them is which path they explore next, and how much they know about where the goal is.
Uninformed
No idea where the goal is. Breadth-first explores level by level, depth-first dives down one branch, and uniform-cost (Dijkstra) always extends the cheapest path.
Informed
Uses a heuristic, an estimate of the distance to the goal. Greedy best-first chases the estimate, and A* balances it against the cost so far.
Adversarial
Another player moves too. Minimax with alpha-beta pruning and Monte Carlo tree search plan against an opponent.
In the graph above, breadth-first search returns S → A → C → G because it has the fewest steps, but it costs 10. Greedy search follows the lowest estimates to S → B → D → G and pays 12. Uniform-cost and A* both find the cheapest path, cost 9, and A* gets there by exploring fewer dead ends. A* is guaranteed to find the cheapest path when its heuristic is admissible, meaning it never overestimates.
Search is easiest to understand by watching the frontier grow. These interactive tutorials and visualizations cover the algorithms in far more depth than this page.
A* is short enough to read in one go. It is Dijkstra's algorithm with one change: the priority adds the heuristic to the cost so far. It uses Python's heapq as the frontier and runs on the graph above.
import heapq
graph = {
'S': {'A': 1, 'B': 4},
'A': {'B': 2, 'C': 6},
'B': {'D': 2},
'C': {'G': 3},
'D': {'C': 1, 'G': 6},
'G': {},
}
h = {'S': 8, 'A': 7, 'B': 6, 'C': 3, 'D': 4, 'G': 0}
def a_star(graph, h, start, goal):
frontier = [(h[start], 0, [start])]
best = {start: 0}
while frontier:
_, cost, path = heapq.heappop(frontier)
node = path[-1]
if node == goal:
return cost, path
for neighbor, step in graph[node].items():
new_cost = cost + step
if new_cost < best.get(neighbor, float('inf')):
best[neighbor] = new_cost
heapq.heappush(frontier, (new_cost + h[neighbor], new_cost, path + [neighbor]))
return None
print(a_star(graph, h, 'S', 'G'))
Output: (9, ['S', 'A', 'B', 'D', 'C', 'G']). Drop the h[neighbor] term and it becomes uniform-cost search. Libraries such as NetworkX include ready-made versions of all of these.
The number of paths grows exponentially with depth. A chess position has about 35 legal moves, so looking just 6 moves ahead means about 1.8 billion positions. Some problems are believed to have no fast exact solution at all, which is why AI leans on heuristics, pruning, and good-enough answers. Growth rates are easier to feel than to read: Toptal's sorting algorithm animations race O(n log n) and O(n2) methods side by side, and the gap widens fast as the input grows. Search costs grow the same way, only faster. To go deeper:
The same idea, exploring possibilities toward a goal, runs through AI from its first programs to today's agents.
Game Playing
Deep Blue searched millions of chess positions per second with minimax and alpha-beta pruning. AlphaGo paired Monte Carlo tree search with neural networks that judge positions. See the History of AI.
Navigation & Robotics
A* and its variants plan routes for map apps, game characters, and robots. The Shakey project invented A* in 1968. See Cognitive Robotics.
Language
The Viterbi algorithm searches for the most likely part-of-speech tags, and beam search picks the output sentence in neural machine translation and text generation.
Planning
Automated planners search over sequences of actions to schedule tasks, route deliveries, and sequence robot assembly.
AI Agents & LLM Reasoning
AI agents try steps, check results, and backtrack. Methods like Tree of Thoughts make this explicit, searching over an LLM's possible reasoning steps.
Learning Instead of Searching
When the costs and transitions aren't known in advance, reinforcement learning learns them by trial and error. Modern systems often combine the two.