Problem-Solving as Search

You’re standing at the start of a maze. You can see only the doorways from your current square. How do you find the exit? That’s the question search algorithms solve — and there are surprisingly few flavours of answer. Before any of them, though, you have to do one thing: turn the puzzle into a shape the algorithms can read.

That shape is called a search problem. Once a navigation app, a Rubik’s-cube solver, an 8-puzzle, or a route planner is written in this shape, the same handful of algorithms solves all of them. The same framing powers production systems you’ll meet on the job — route optimisers, robot motion planners, even the move-search inside game and RL agents all start by casting the task as states, actions, and a goal.

The five pieces of a search problem

Every search problem is a tuple of exactly five things:

• States — the configurations you can be in (a maze cell, a board layout, a city).
• Actions — what you can do from a state (move north, swap two tiles, drive an edge).
• Transition model — for each state and action, the state you land in next.
• Goal test — a function that says “are we done?” for a given state.
• Path cost — a number you pay per action; the goal is the cheapest path, not just any.

The initial state is where you start. A solution is a sequence of actions that moves you from the initial state to one that passes the goal test. A best solution minimises the total path cost.

The search tree

Starting from the initial state, expand each state by listing its successors under it. Repeat. You get a search tree — the algorithm’s view of the world.

A subtle but important point: the state space (the underlying graph of configurations) is fixed by the problem; the search tree is built by the algorithm as it explores. The same state can appear at many different tree nodes, once per path that reaches it.

The width of the tree at one level is the branching factor b (how many actions per state, on average). The depth of the shallowest goal is d. Almost every cost estimate you will see in the next lesson is some function of b and d — there are about b^d nodes at depth d, so the tree balloons fast.

Tree search vs graph search

Read the right-hand tree above carefully. From A you can go to B (cost 2) or C (cost 3). From B you can go back to A or onward to D. A tree-search algorithm happily expands that returning A again, then expands its children again, then their children — looping forever on any state space with a cycle.

A graph-search algorithm keeps a visited (or “explored”) set. Before adding a node to the search tree, it checks: have we already expanded this state? If yes, skip it. The greyed-out A’s in the diagram are the nodes graph search refuses to expand a second time.

graph_search(problem):
    frontier = [initial_state]
    explored = {}            # the only difference from tree search
    while frontier not empty:
        node = pop(frontier)
        if goal_test(node): return path_to(node)
        add node.state to explored
        for action in actions(node.state):
            child = transition(node.state, action)
            if child not in explored and child not in frontier:
                add child to frontier

That single explored set is the difference between “always works” and “loops forever”.

Worked example

A small road network: nodes are the cities A, B, C, D, E. Edges (with distances): A-B: 2, A-C: 5, B-D: 4, C-D: 1, D-E: 3. Formulate “shortest path from A to D” as a search problem.

Pieces, in order:

• States — the five cities {A, B, C, D, E} (one per node).
• Actions — at a state, “drive to neighbour X” for each neighbour X.
• Transition model — applying “drive to X” from state Y lands in state X.
• Goal test — state == D.
• Path cost — sum of edge distances along the path.

Now the search tree from A: depth 0 is just A. Depth 1 expands to B (via A-B, cost 2) and C (via A-C, cost 5). Depth 2 expands B to A (back) and D (cost 2 + 4 = 6), and C to A (back) and D (cost 5 + 1 = 6). Two paths to D, both cost 6. Tree search would keep going through the back-edges to A; graph search would prune them.

That’s the whole formulation. From here, the algorithm of the next lesson — BFS, DFS, UCS, or IDDFS — just walks this tree by a particular rule.

How GATE asks this

A typical MCQ gives you a tiny scenario — a maze, a sliding puzzle, a route map — and asks you to identify one of the five pieces: “Which of the following is the state space for the 8-puzzle?” or “What is the goal test in a route-finding problem?” The vocabulary itself (state, action, transition, goal test, path cost) is the answer. The other recurring question is conceptual: which search algorithm avoids re-expanding states? Answer: graph search.

Quick check