Problem-Solving as Search

The machine-learning chapter just closed on a problem with no data to learn from — a maze, a game, a route — where the answer has to be reasoned out from rules and a goal. So stand at the start of that maze now. You can see only the doorways leading off your current square. How do you find the exit? That is the question search algorithms answer, and there are surprisingly few flavours of answer. But before any algorithm can run, you must do one thing: cast the puzzle into a shape the algorithms can read.

That shape is a search problem, and its reach is the surprise. Write a navigation app, a Rubik’s-cube solver, an 8-puzzle, or a route planner in this one shape, and the same handful of algorithms solves all of them. The same framing drives production systems too — route optimisers, robot motion planners, the move-search inside game and reinforcement-learning agents — every one of them begins 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 aim is the cheapest path, not just any.

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

The search tree

Starting from the initial state, expand each state by listing its successors beneath it. Repeat. You get a search tree — the algorithm’s unfolding 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 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 its children again, then theirs — 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.

Name the five 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 — the sum of edge distances along the path.

Now unfold 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 reach D, both costing 6 — a tie, as the prompt invited you to suspect. Tree search would keep grinding through the back-edges to A; graph search would prune them.

That is 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 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.

In one breath

A search problem casts any rules-and-goal puzzle into five pieces — states, actions, a transition model, a goal test, and a path cost — after which the same algorithms solve them all; expanding successors from the initial state unfolds a search tree (the same state can recur at many nodes) whose size is about b^d for branching factor b and goal depth d, and the crucial safeguard is that graph search keeps an explored set to skip already-seen states, where pure tree search keeps no memory and loops forever on any cyclic space.

Practice

A question to carry forward

You can now lay any puzzle out as a search tree — but laying it out is not solving it. The tree just sits there, a branching cloud of possibilities; something has to actually walk it, node by node, until it stumbles on the goal. And the order of that walk is everything.

Do you fan out level by level, checking every square one step away before any square two steps away? Or plunge straight down one branch to its end before backing up? Or always extend whichever path is cheapest so far? Each strategy walks the very same tree, yet they differ wildly in whether they are guaranteed to find a solution at all, whether they find the cheapest one, and how much memory they devour doing it. Here is the thread onward: what are the handful of label-free, “uninformed” strategies for ordering that walk — BFS, DFS, UCS, IDDFS — and how do completeness, optimality, time, and space sort them apart?