Search & problem solving: BFS, DFS and A*

Long before machine learning became popular, AI systems solved problems by searching. Route planners, puzzle solvers, timetable builders and game engines still work this way. The idea is simple: describe the problem as a set of states and the actions that move between them, then explore that space in a smart order.

Modelling a problem as a state space

Four things define a search problem:

• Initial state — where you start (say, Rajiv Chowk metro station).
• Actions — what you can do from a state (ride one stop to a neighbouring station).
• Goal test — how you know you are done (you reached Huda City Centre).
• Path cost — what a path costs (minutes travelled, fuel spent, rupees).

Breadth-first search

BFS explores the graph level by level, so on an unweighted graph it returns the path with the fewest steps.

from collections import deque

metro = {
    "Rajiv Chowk": ["Kashmere Gate", "Central Secretariat", "Karol Bagh"],
    "Central Secretariat": ["Rajiv Chowk", "Hauz Khas"],
    "Hauz Khas": ["Central Secretariat", "Huda City Centre"],
    "Kashmere Gate": ["Rajiv Chowk"],
    "Karol Bagh": ["Rajiv Chowk"],
    "Huda City Centre": ["Hauz Khas"],
}

def bfs(graph, start, goal):
    queue = deque([[start]])
    seen = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for nxt in graph.get(node, []):
            if nxt not in seen:
                seen.add(nxt)
                queue.append(path + [nxt])
    return None

print(bfs(metro, "Rajiv Chowk", "Huda City Centre"))

Depth-first search

DFS goes deep down one branch before backtracking. Swap popleft() for pop() above and you have DFS. It uses far less memory than BFS, but it can wander down a long branch and return a poor path — or loop forever on an infinite space unless you track visited states or cap the depth.

A*: search with a hint

Real maps have costs, and blind search wastes time. A* orders the frontier by f(n) = g(n) + h(n), where g is the cost already paid and h is a heuristic estimate of the cost still to come (for roads, straight-line distance).

import heapq

def a_star(graph, start, goal, h):
    frontier = [(h(start), 0, start, [start])]
    best = {start: 0}
    while frontier:
        _, g, node, path = heapq.heappop(frontier)
        if node == goal:
            return path, g
        for nxt, step_cost in graph[node]:
            new_g = g + step_cost
            if new_g < best.get(nxt, float("inf")):
                best[nxt] = new_g
                heapq.heappush(frontier, (new_g + h(nxt), new_g, nxt, path + [nxt]))
    return None, float("inf")

A* is guaranteed to find the cheapest path only if the heuristic is admissible — it never overestimates the real remaining cost. Straight-line distance is admissible for road travel because no road is shorter than a straight line.

Common mistakes

• Forgetting a seen set, so the search revisits states and never ends.
• Using DFS when the shortest route matters.
• Inventing a heuristic that overestimates (for example, multiplying distance by 1.5 for traffic) and then being surprised that A* returns a sub-optimal route.
• Building the full state space in memory when you only need to generate neighbours on demand.