Search Algorithms in AI: How Machines Find Solutions Step by Step

The State Space

The set of all possible configurations the problem can be in. For a GPS, this is every possible location on the map. For a puzzle like the 8-puzzle, it’s every possible arrangement of the tiles. The state space can be enormous—a chess game has more possible states than atoms in the observable universe—which is why smart search matters.

The Initial State

Where the search begins. Your current location on a map. The starting arrangement of puzzle pieces. The beginning of a maze.

The Goal Test

A function that determines whether a given state is a solution. For navigation, “are we at the destination address?” For chess, “is the opponent in checkmate?” Sometimes there’s one specific goal state; other times, any state satisfying certain conditions works.

Actions and Transitions

What moves are legal from any given state, and what new state results from taking that action. In a maze, the actions are “move up, down, left, right” and the transition model says “if you move up from (3,4), you arrive at (3,5) unless there’s a wall.”

Breadth-First Search (BFS)

How it works step by step:

1. Place the initial state in the queue.
2. Remove the front node from the queue. If it’s a goal, return the solution.
3. Generate all successor nodes (neighbors) of the current node.
4. For each successor not already explored, add it to the back of the queue.
5. Repeat from step 2 until the queue is empty (no solution) or goal found.

Visual intuition: BFS explores in concentric rings around the start state. First all states 1 step away, then all states 2 steps away, and so on. This guarantees the shortest path in terms of number of steps, but the frontier can grow exponentially.

from collections import deque

def bfs(start, is_goal, get_neighbors):
    visited = set([start])
    queue = deque([(start, [start])])  # Store path with node
    
    while queue:
        node, path = queue.popleft()
        if is_goal(node):
            return path
        
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

Depth-First Search (DFS)

How it works step by step:

1. Place the initial state on the stack.
2. Pop the top node from the stack. If it’s a goal, return the solution.
3. Generate all successor nodes.
4. Push unvisited successors onto the stack (order determines exploration order).
5. Repeat from step 2 until stack is empty or goal found.

Visual intuition: DFS plunges down a single path as far as possible before backtracking. It uses far less memory than BFS because it only stores the current path, not an entire frontier level. However, it may find a long, meandering solution while a much shorter path exists.

def dfs(node, is_goal, get_neighbors, visited=None, path=None):
    if visited is None:
        visited = set()
        path = []
    
    visited.add(node)
    path = path + [node]
    
    if is_goal(node):
        return path
    
    for neighbor in get_neighbors(node):
        if neighbor not in visited:
            result = dfs(neighbor, is_goal, get_neighbors, visited, path)
            if result:
                return result
    return None

A* Search: The Gold Standard

How it works step by step:

1. Place the initial state in a priority queue, ordered by f(n) = g(n) + h(n).
   • g(n) = actual cost from start to current node
   • h(n) = estimated cost from current node to goal (the heuristic)
2. Remove the node with lowest f(n) from the priority queue. If it’s a goal, return the solution.
3. Generate all successors.
4. For each successor:
   • Calculate tentative g = g(current) + cost(current, successor)
   • If this path is better than any previously known path to successor, update g(successor) and f(successor)
   • Add to priority queue (or update its position if already present)
5. Repeat from step 2 until queue is empty or goal found.

import heapq

def a_star(start, is_goal, get_neighbors, cost_func, heuristic):
    counter = 0  # For tie-breaking
    open_set = [(heuristic(start), counter, start, [start], 0)]
    heapq.heapify(open_set)
    visited = {}
    
    while open_set:
        f, _, node, path, g = heapq.heappop(open_set)
        
        if node in visited and visited[node] <= g:
            continue
        visited[node] = g
        
        if is_goal(node):
            return path
        
        for neighbor in get_neighbors(node):
            new_g = g + cost_func(node, neighbor)
            new_f = new_g + heuristic(neighbor)
            counter += 1
            heapq.heappush(open_set, (new_f, counter, neighbor, 
                                      path + [neighbor], new_g))
    return None

The magic of the heuristic: The heuristic h(n) estimates the remaining cost. For A* to guarantee optimal solutions, h(n) must be admissible—it must never overestimate the true cost. For grid pathfinding, Manhattan distance is the classic admissible heuristic: you can't reach the goal in fewer steps than the sum of horizontal and vertical distances.