Search Algorithms for AI Problem Solving

"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

A directed weighted graph from start S to goal G, with step costs on each edge and a heuristic estimate on each node. The cheapest path S, A, B, D, C, G costs 9.
Problem Solving as Search

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
Families of Search

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.

See It in Action

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* in Python

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.

Why Search Gets Hard

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:

Search in AI Problem Solving

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.

Side note: when only the final answer matters and not the path, such as the best schedule or design, local search takes over. That leads into AI-driven optimization, including genetic algorithms and swarm intelligence.
Content created in collaboration with Claude.