State-space search: BFS, DFS, UCS and A* with animations

A search problem is a six-tuple

P = (S, s₀, A, T, G, c)

that satisfies:

1. S is a non-empty set; its elements are called states;
2. s₀ ∈ S; this state is called the initial state;
3. A assigns to every state s ∈ S a finite set A(s) of actions applicable in state s; let 𝒟 = {(s, a) : s ∈ S, a ∈ A(s)} denote the set of all pairs “state, action applicable in it”;
4. T : 𝒟 → S is the transition function; for (s, a) ∈ 𝒟 the state s′ = T(s, a) is a successor of state s (after action a);
5. G ⊆ S is the set of goal states;
6. c : 𝒟 → ℝ⁺ = (0, ∞) is the action cost: c(s, a) > 0 is the cost of applying action a in state s.

So the problem says exactly where we start, which moves are available in each state, where each move leads, how much it costs and when we are at the goal.

Let P = (S, s₀, A, T, G, c) be a search problem and k ∈ ℕ₀. A path of length k from the initial state is a sequence

π = (s₀, a₁, s₁, a₂, …, a_k, s_k)

such that for every i = 1, …, k we have a_i ∈ A(s_i−1) and s_i = T(s_i−1, a_i). (For k = 0 the path is just (s₀).)

The cost of the path π is the sum of the costs of its actions:

g(π) = ∑_i=1^k c(s_i−1, a_i).

A path π is a solution if and only if s_k ∈ G. Let Π denote the set of all solutions. If Π ≠ ∅, the optimal cost is

C* = min {g(π) : π ∈ Π}

(if the minimum exists; in problems with finitely many states, like our maze, it always does) and a solution π is optimal if and only if g(π) = C*. An optimal solution is thus a solution that is not more expensive than any other solution.

Eight tiles and the empty space can be placed into nine cells in 9! = 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 362,880 ways. By sliding, though, you can reach only half of them: if you write the tiles down row by row (without the empty space), every move preserves whether that order contains an even or an odd number of “larger before smaller” pairs. A horizontal move does not change the order at all, a vertical move makes a tile jump over two others and changes the number of such pairs by 0 or by ±2. A state with the opposite parity therefore cannot be reached. That exactly half of the states are reachable (for the 15-puzzle with a slightly more complicated invariant that also involves the row of the empty space) was proved by W. W. Johnson and W. E. Story in 1879.

8-puzzle: 9!/2 = 362,880/2 = 181,440 states.
15-puzzle: 16!/2 = 20,922,789,888,000/2 = 10,461,394,944,000 ≈ 1.05 · 10¹³ states — over ten trillion.

We write a cell as a pair (r, s) — row r ∈ {0, …, 8}, column s ∈ {0, …, 13}. Let Z be the set of walls and B the set of mud cells.

• States: S = ({0, …, 8} × {0, …, 13}) ∖ Z — every cell except the walls.
• Initial state: s₀ = (0, 0). Goal: G = {(8, 13)}.
• Moves: ↑ = (−1, 0), → = (0, 1), ↓ = (1, 0), ← = (0, −1). The actions applicable in state (r, s) ∈ S are those that lead to a cell inside the grid that is not a wall: A((r, s)) = {(Δr, Δs) ∈ {↑, →, ↓, ←} : (r + Δr, s + Δs) ∈ S}.
• Transition: T((r, s), (Δr, Δs)) = (r + Δr, s + Δs), e.g. T((r, s), →) = (r, s + 1).
• Cost: c(x, a) = 5 if T(x, a) ∈ B, otherwise c(x, a) = 1 — you pay for the cell you step onto.
• Task: find a solution with the lowest cost C*.

Let P = (S, s₀, A, T, G, c) be a search problem. For a state s ∈ S, denote the set of its successors

N(s) = {T(s, a) : a ∈ A(s)}.

At every moment of its run a search algorithm maintains two sets of states:

1. the frontier F ⊆ S — states the algorithm has already discovered (a path found from s₀ leads to them) but not yet expanded; at the start F = {s₀};
2. the closed states E ⊆ S — states it has already expanded; at the start E = ∅.

To expand a state s ∈ F means to make these two changes (in this order):

E ← E ∪ {s},   F ← (F ∖ {s}) ∪ (N(s) ∖ E).

The expanded state thus moves from the frontier to the closed states, and those of its successors that have not been expanded yet are added to the frontier.

Input: a search problem P = (S, s₀, A, T, G, c). Output: a solution (a path from s₀ to some state in G), or the message “no solution exists”.

Breadth-first search (BFS) is the common skeleton above in which the frontier F is a queue (FIFO, first in — first out):

1. F ← (s₀), E ← ∅.
2. If F is empty, stop: no solution exists.
3. Remove from F the state s that entered it first.
4. If s ∈ G, stop and return the path from s₀ to s.
5. Expand s: add it to E and append every successor s′ ∈ N(s) that is neither in E nor in F to the end of F. Continue with step 2.

Properties. Let d(s) denote the depth of state s — the smallest length of a path from s₀ to s. BFS expands states in non-decreasing order of d(s), and therefore returns the solution with the fewest actions. Let b = max_{s ∈ S} |A(s)| be the branching factor (the largest number of successors of a state) and d the depth of the shallowest solution. Then BFS generates at most b + b² + … + b^d = O(b^d) states and keeps just as many in memory.

The BFS path has 25 steps, 3 of them into mud: g = 22 · 1 + 3 · 5 = 22 + 15 = 37.

The size of the ripple for branching factor b = 10: at depth d = 5 it is 10 + 100 + 1,000 + 10,000 + 100,000 = 111,110 states, at depth d = 10 already 11,111,111,110 ≈ 1.1 · 10¹⁰. If one state took 1 kB of memory, the ripple at depth 10 would need over 11 TB. Every further level multiplies that by ten.

Input: a search problem P = (S, s₀, A, T, G, c). Output: a solution, or the message “no solution exists”.

Depth-first search (DFS) is the common skeleton above in which the frontier F is a stack (LIFO, last in — first out):

1. F ← (s₀), E ← ∅.
2. If F is empty, stop: no solution exists.
3. Remove from F the state s that entered it last (the top of the stack).
4. If s ∈ G, stop and return the path from s₀ to s.
5. Expand s: add it to E and push every successor s′ ∈ N(s) ∖ E onto the top of F. Continue with step 2.

Properties. Let b be the branching factor and m the maximum depth of the state space (the largest length of a path without repeated states, possibly ∞). In the tree variant (without the set E; repeated states are checked only on the current branch) DFS keeps only the current branch and its siblings in memory: O(b · m) states. Time is O(b^m) in the worst case. DFS is not optimal, and in an infinite space it is not even complete — it can keep descending forever.

Input: a search problem P = (S, s₀, A, T, G, c). Output: a solution with the fewest actions (if any solution exists).

For ℓ ∈ ℕ₀, let DLS(ℓ) (depth-limited search) denote depth-first search that does not expand states at depth ℓ or more — so it does not examine paths longer than ℓ. Iterative deepening (IDDFS):

1. ℓ ← 0.
2. Run DLS(ℓ).
3. If DLS(ℓ) found a solution, stop and return it.
4. ℓ ← ℓ + 1 and continue with step 2.

Stopping condition: the first ℓ for which DLS(ℓ) finds a solution; that is exactly the depth d of the shallowest solution. (If no solution exists and the space is infinite, the algorithm does not terminate.)

Properties. Let b be the branching factor and d the depth of the shallowest solution. States at depth i ∈ {1, …, d} are generated (d − i + 1) times, in total ∑_i=1^d (d − i + 1) · bⁱ = O(b^d) states — the same as BFS, but with memory of only O(b · d).

Input: a search problem P = (S, s₀, A, T, G, c). Output: a solution with the lowest cost, or the message “no solution exists”.

During the run the algorithm assigns to every discovered state n ∈ S a number g(n) — the cost of the cheapest path from s₀ to n found so far. The frontier F is a priority queue ordered by g. Uniform-cost search (UCS):

1. F ← {s₀}, g(s₀) ← 0, E ← ∅.
2. If F = ∅, stop: no solution exists.
3. Remove from F the state n with the lowest g(n).
4. If n ∈ G, stop and return the path found to n (its cost is g(n)).
5. Add n to E. For every action a ∈ A(n) and n′ = T(n, a) ∉ E: if n′ ∉ F, or g(n) + c(n, a) < g(n′), set g(n′) ← g(n) + c(n, a), remember n as the predecessor of n′ and insert n′ into F. Continue with step 2.

Properties. Suppose there is an ε > 0 such that c(s, a) ≥ ε for all s ∈ S, a ∈ A(s). Then UCS expands states in non-decreasing order of g, and is therefore complete and optimal. The number of expanded states is O(b^{1 + ⌊C*/ε⌋}), where b is the branching factor and ⌊x⌋ the floor of the number x.

The first ten expansions with their value of g: (0, 0) g = 0; (0, 1) g = 1; (1, 0) g = 1; (0, 2) g = 2; (2, 0) g = 2; (0, 3) g = 3; (3, 0) g = 3; (1, 3) g = 4; (4, 0) g = 4; (2, 3) g = 5. Until it runs into mud, UCS expands just like BFS, because every step costs 1 and g is simply the depth. Mud then “pushes back” a state by 5 instead of 1 — UCS looks into the mud only once it has used up everything cheaper.

The path found: 25 steps on dry ground, C* = 25 · 1 = 25. The smallest action cost is ε = 1 and the branching factor b = 4, so the upper bound is b^{1 + ⌊C*/ε⌋} = 4²⁶ ≈ 4.5 · 10¹⁵ states. In reality UCS expanded 49 cells: the bound assumes an infinite tree where nothing repeats, whereas the maze has only 83 passable cells and closed states are not expanded again.

Let P = (S, s₀, A, T, G, c) be a search problem. For a state n ∈ S, let h*(n) ∈ ℝ_≥0 ∪ {∞} denote the lowest cost (more precisely the infimum of the costs) of paths from state n to some goal state (a path is defined as above, it just starts in n instead of s₀; if no path leads from n to G, then h*(n) = ∞). A heuristic is a function

h : S → ℝ_≥0  such that  ∀n ∈ G : h(n) = 0.

We read the value h(n) as an estimate of h*(n). A heuristic h is

1. admissible if and only if ∀n ∈ S : h(n) ≤ h*(n);
2. consistent (monotone) if and only if ∀n ∈ S ∀a ∈ A(n) : h(n) ≤ c(n, a) + h(T(n, a)).

An admissible heuristic thus never overestimates the real remaining cost; a consistent heuristic never drops after a step by more than that step cost. Every consistent heuristic is admissible (theorem below).

Let P = (S, s₀, A, T, G, c) be a search problem and h : S → ℝ_≥0 a consistent heuristic. Then h is admissible, i.e. h(n) ≤ h*(n) for every n ∈ S.

Proof. Let n ∈ S. If h*(n) = ∞, the inequality holds trivially. Otherwise take any path from n to a goal: n = n₀, n₁, …, n_k ∈ G, where n_i = T(n_i−1, a_i) and c_i = c(n_i−1, a_i) for i = 1, …, k. We apply consistency k times in a row:

h(n₀) ≤ c₁ + h(n₁) ≤ c₁ + c₂ + h(n₂) ≤ … ≤ c₁ + … + c_k + h(n_k).

At the goal h(n_k) = 0, so h(n) is at most the cost of this path. That holds for every path from n to a goal, hence also for the cheapest one, whose cost is h*(n). Therefore h(n) ≤ h*(n). ∎

The converse does not hold: an admissible heuristic need not be consistent.

Input: a search problem P = (S, s₀, A, T, G, c) and a heuristic h : S → ℝ_≥0. Output: a solution, or the message “no solution exists”.

Greedy best-first search is the common skeleton above in which the frontier F is a priority queue ordered by

f(n) = h(n):

1. F ← {s₀}, E ← ∅.
2. If F = ∅, stop: no solution exists.
3. Remove from F the state n with the lowest h(n) — the state estimated to be closest to the goal.
4. If n ∈ G, stop and return the path from s₀ to n.
5. Expand n: add it to E and insert every successor n′ ∈ N(n) that is neither in E nor in F into F. Continue with step 2.

The cost so far, g(n), is not taken into account. Properties: greedy search is not optimal; with repeated-state checking (the set E) it is complete in a finite space.

Expanded cells with their value of h: (0, 0) 21 → (0, 1) 20 → (0, 2) 19 → (0, 3) 18 → (1, 3) 17 → (2, 3) 16 → (2, 2) 17 → (3, 2) 16 → (4, 2) 15 → (4, 3) 14.

Greedy search heads straight right and down as long as h decreases. In the seventh step h briefly rises (from 16 to 17), because from (2, 3) no path leads further right or down (walls) and there is no cell with a smaller h left in the frontier. Two steps later it steps into the mud at (4, 2), because that way h decreases again. It does not see the cost of 5 for a step into the mud at all: the priority is only h, no g.

Input: a search problem P = (S, s₀, A, T, G, c) and a heuristic h : S → ℝ_≥0. Output: a solution, or the message “no solution exists”.

A* is UCS (steps 1–5 of its definition above, including maintaining g) in which the frontier F is a priority queue ordered by

f(n) = g(n) + h(n)

instead of by g(n): in step 3 the state with the lowest f(n) is removed from F. The value f(n) is an estimate of the cost of the whole path from the start through n to the goal. The algorithm stops as soon as it removes a goal state from F (or when F is empty).

Theorem. Let h be a consistent heuristic and let action costs be ≥ ε for some ε > 0. Then the values of f along every path are non-decreasing, A* expands states in non-decreasing order of f, and the first goal state expanded lies on an optimal path with cost C*. In doing so it expands every state with f(n) < C* and none with f(n) > C*.

For h ≡ 0, A* is the same as UCS; without g it would be greedy search.

Let h be a consistent heuristic, f = g + h, n ∈ S, a ∈ A(n), n′ = T(n, a), and let the path to n′ go through n, so that g(n′) = g(n) + c(n, a). Then f(n′) ≥ f(n).

Proof. f(n′) = g(n) + c(n, a) + h(n′) ≥ g(n) + h(n) = f(n),

where the inequality is exactly the consistency h(n) ≤ c(n, a) + h(n′). ∎

From this it follows (here only as a sketch) that A* expands states in non-decreasing order of f: if it later expanded a state with a smaller f, the frontier would have to contain on the way to it a state with an even smaller f, which should have come first. So when the goal is expanded for the first time (where h = 0 and f = g), no cheaper path remains.

Let 𝒜 be an algorithm that receives a search problem P as input and returns a solution, or the message “no solution exists”. The algorithm 𝒜 is

1. complete if and only if for every problem P that has at least one solution (Π ≠ ∅), 𝒜 stops after a finite number of steps and returns a solution π ∈ Π;
2. optimal if and only if for every problem P with Π ≠ ∅ it returns a solution π with cost g(π) = C*.

The parameters that time and memory depend on (for a problem P = (S, s₀, A, T, G, c)):

1. b = max_{s ∈ S} |A(s)| — the branching factor;
2. d — the depth of the shallowest solution (the smallest length of a path from s₀ to G);
3. m — the maximum depth of the space (the largest length of a path from s₀ without repeated states, possibly ∞);
4. C* — the optimal cost, and ε > 0 — a lower bound on the action costs.

For functions u, v ≥ 0 of these parameters we write u = O(v) if and only if there exist constants K > 0 and x₀ such that u(x) ≤ K · v(x) for all x ≥ x₀. O(·) thus states how time (the number of generated states) or memory (the number of states held at once) grow at most with these parameters, up to a constant factor.

Let S be a non-empty set of states, f : S → ℝ a function (the objective function) and N : S → 2^S a map that assigns to every state s ∈ S a finite non-empty set N(s) ⊆ S ∖ {s} (the neighbourhood of state s; its elements are neighbours). The local search problem is to find a state

s* ∈ argmax_{s ∈ S} f(s) = {s ∈ S : ∀s′ ∈ S : f(s) ≥ f(s′)},

or at least a state with as large a value of f as possible. A state s ∈ S is

1. a local maximum if and only if ∀s′ ∈ N(s) : f(s) ≥ f(s′);
2. a global maximum if and only if ∀s′ ∈ S : f(s) ≥ f(s′).

Every global maximum is also a local one; the converse does not hold.

Hill climbing. Input: S, f, N as above and an initial state s ∈ S. Output: a local maximum.

1. Choose s′ ∈ argmax_{t ∈ N(s)} f(t) (the best neighbour).
2. If f(s′) ≤ f(s), stop and return s — it is a local maximum.
3. Otherwise s ← s′ and continue with step 1.

A state is a number s ∈ [0, 1], the neighbourhood is the two points 0.02 to the left and to the right: N(s) = {s − 0.02, s + 0.02}. The landscape has two peaks (a local one at s = 0.25, the global one at 0.72) and the climber starts from s = 0.05.

In every row the right neighbour is the highest, so the climber goes right. In the last row both neighbours (0.582) are lower than f(0.25) = 0.600 and the algorithm stops — at a local maximum, even though the global maximum has f(0.72) = 0.950.

Input: S, f, N as in local search, an initial state s ∈ S, an initial temperature T₀ > 0, a cooling coefficient q ∈ (0, 1) and a minimum temperature T_min ∈ (0, T₀). Output: a state s ∈ S.

1. T ← T₀.
2. If T ≤ T_min, stop and return s.
3. Pick a neighbour s′ ∈ N(s) at random (uniformly) and compute Δ = f(s′) − f(s).
4. If Δ > 0, set s ← s′. If Δ ≤ 0, set s ← s′ with probability exp(Δ/T), otherwise keep s.
5. T ← q · T and continue with step 2.

The “temperature” T thus gradually falls to zero, and with it the willingness to accept a worse neighbour. (Cooling T ← q · T is the most common choice; other schedules are used too.)