Problem Solving as Search

Before a problem can be searched it has to be described in a particular way. The description is deliberately spare, and that spareness is what lets one algorithm solve route planning, puzzle solving, and scheduling without knowing which of them it is working on.

The five parts of a search problem

A search problem is given by an initial state, a set of actions available in each state, a transition model saying which state each action leads to, a goal test, and a step cost for each action. Together the first three implicitly define the state space: the graph of every state reachable from the start.

The word implicitly is doing the work. The state space is never written down. It is generated on demand, one successor at a time, which is what makes it possible to search spaces with more states than there are atoms in the observable universe. A solution is a sequence of actions from the initial state to a goal, and an optimal solution is one of least total cost.

Four questions to ask about any strategy

Every strategy in this lesson is judged on the same four criteria:

• Completeness - if a solution exists, is the algorithm guaranteed to find it?
• Optimality - does it find the cheapest solution?
• Time complexity - how many nodes does it generate?
• Space complexity - how many does it hold in memory at once?

Complexity is expressed in the branching factor $b$, the number of successors per node, and the depth $d$ of the shallowest goal.

Breadth-first and the memory wall

Breadth-first search expands the shallowest unexpanded node, so it finds a shallowest goal. It is complete when $b$ is finite, and it generates on the order of $b^d$ nodes provided the goal test is applied to each node as it is generated. Delay the test to expansion, as uniform-cost search has to, and the whole next level is generated first: $O(b^{d+1})$.

The trap is the space. The whole frontier is held at once, so memory is $O(b^d)$ too - the same exponential as the time. Russell & Norvig tabulate what that means with $b = 10$ at a million nodes per second and a kilobyte per node, and draw the lesson plainly:

the memory requirements are a bigger problem for breadth-first search than is the execution time.

A search to depth 12 takes about thirteen days, which one might wait out. It also needs a petabyte of memory, which no ordinary machine has. Time is a nuisance; memory is a wall.

There is a second limitation. Breadth-first search returns the shallowest goal, which is the cheapest goal only if every step costs the same. When step costs differ, the fix is uniform-cost search: expand the node with the lowest path cost $g(n)$ rather than the lowest depth. It is optimal for any non-negative step costs, though it can waste effort exploring large trees of tiny steps before it ever tries a big one.

Depth-first and iterative deepening

Depth-first search goes as deep as it can before backtracking, so it stores only the current path and its unexpanded siblings: memory $O(bm)$ for maximum depth $m$. That is a dramatic saving. The price is that it is neither optimal nor - on an infinite or looping space - complete.

Iterative deepening takes the good half of each. Run a depth-limited search with limit 0, then 1, then 2, until a goal is found:

The two $O(b^d)$ rows, and the thirteen days and the petabyte above, assume the goal test on generation; at expansion each becomes $O(b^{d+1})$.

The obvious objection is that the upper levels are regenerated on every iteration. The answer is that in a tree with a roughly constant branching factor almost all the nodes are in the bottom level, which is generated only once, so the repetition costs a constant factor while the memory saving is exponential. That is why iterative deepening is the standard uninformed method when the space is large and the solution depth is unknown.

Before the quiz

Be able to state the five parts of a search problem, list the four evaluation criteria, give the time and space complexity of each strategy above, say precisely when breadth-first search is optimal, and explain the trade that makes iterative deepening worth its repeated work. The next module adds a heuristic and asks how much of this space can be skipped.