Uninformed Search Strategies

Source: Unit 1 §3

Uninformed (blind) search uses only the information in the problem definition. It has no extra knowledge about states: all it can do is generate successors and tell a goal from a non-goal. Every strategy below differs from the others in exactly one way, the order of node expansion.

The five strategies are BFS, UCS, DFS, DLS and IDS.

Breadth-first search

BFS expands the root, then every successor of the root, then all of their successors. All nodes at a given depth are expanded before any node at the next level, which falls straight out of using a FIFO queue for the frontier.

BFS with a FIFO frontier: level by level, left to right.

function BREADTH-FIRST-SEARCH(problem) returns solution or failure

node ← node with STATE = problem.INITIAL-STATE, PATH-COST = 0

if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

frontier ← a FIFO queue with node as the only element

explored ← empty set

loop do

if EMPTY?(frontier) then return failure

node ← POP(frontier) /* shallowest node in frontier */

add node.STATE to explored

for each action in problem.ACTIONS(node.STATE) do

child ← CHILD-NODE(problem, node, action)

if child.STATE not in explored or frontier then

if problem.GOAL-TEST(child.STATE) then return SOLUTION(child)

frontier ← INSERT(child, frontier)

Criterion	BFS
Complete?	Yes, if the shallowest goal is at finite depth d and b is finite.
Time	b + b² + b³ + … + bᵈ = O(bᵈ)
Space	O(bᵈ) - every generated node stays in memory: O(b^(d-1)) explored plus O(bᵈ) on the frontier. This is the weakness.
Optimal?	Only if path cost is a non-decreasing function of depth, most commonly when all step costs are equal. Otherwise the shallowest goal need not be the cheapest.

⚠GotchaBFS runs out of memory long before it runs out of time

The space term is the same $O(b^d)$ as the time term, and memory is the scarcer resource. A branching factor of 10 at depth 10 is ten billion nodes held at once. In practice BFS dies of memory exhaustion while the CPU is still willing.

Uniform-cost search

When step costs are equal, expanding the shallowest node is the same as expanding the cheapest one, and BFS is optimal. UCS is the extension for when costs are not uniform: it expands the node $n$ with the lowest path cost $g(n)$, using a priority queue ordered by $g$.

≡FactsThe key formula

$g(n)$ is the total path cost from the start node to node $n$. UCS always expands the smallest $g(n)$ on the frontier.

function UNIFORM-COST-SEARCH(problem) returns solution or failure

node ← node with STATE = INITIAL-STATE, PATH-COST = 0

frontier ← priority queue ordered by PATH-COST, node as only element

explored ← empty set

loop do

if EMPTY?(frontier) then return failure

node ← POP(frontier) /* lowest-cost node */

if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

add node.STATE to explored

for each action in problem.ACTIONS(node.STATE) do

child ← CHILD-NODE(problem, node, action)

if child.STATE not in explored or frontier then

frontier ← INSERT(child, frontier)

else if child.STATE in frontier with higher PATH-COST then

replace that frontier node with child

⚠GotchaTwo differences from BFS that exams test

1. The goal test happens on pop, not on generation. A goal spotted while generating children may still be reachable more cheaply another way, so UCS refuses to commit until that node is the cheapest thing on the frontier.
2. If a cheaper path to a frontier node turns up, the frontier entry is replaced, not added alongside.

UCS returns the path with the lowest total cost, which here is the three-step S→A→C→G (8), not the two-step S→B→G (9).

→StepsThe frontier, spin by spin

1. Expand S, which puts A(5) and B(6) on the frontier, ordered by $g$.
2. Pop the cheapest, A(5), and expand it. That generates C(6), since S→A→C costs $5 + 1 = 6$.
3. The frontier is now C(6), B(6), a tie; expand either.
4. Keep going until a goal node is popped, not merely generated. The answer is the path with the lowest total cost, which need not be the one with the fewest steps.

⚠GotchaZero-cost actions break completeness

UCS counts cost, not steps, so an infinite sequence of zero-cost actions is an infinite loop it will happily follow. Completeness is guaranteed only if every step cost exceeds some small positive constant $\varepsilon$.

Its complexity is quoted in terms of $C^*$, the cost of the optimal solution, and $\varepsilon$, rather than $b$ and $d$.

Criterion	UCS
Complete?	Yes, if every step cost ≥ ε > 0.
Time	O(b^(1 + ⌊C*/ε⌋))
Space	O(b^(1 + ⌊C*/ε⌋))
Optimal?	Yes. Whenever UCS selects a node for expansion, the optimal path to it has already been found.

Depth-first search

DFS always expands the deepest node on the frontier, using a LIFO stack, which is why it is usually written as a recursive function that calls itself on each child in turn.

DFS with a LIFO frontier: plunge to the bottom of the leftmost branch, then backtrack.

Criterion	DFS
Complete?	No. In an infinite-depth space it can follow one branch forever.
Time	O(bᵐ) - terrible when m ≫ d, but much faster than BFS when solutions are dense.
Space	O(b·m) - linear, and the reason DFS survives at all.
Optimal?	No.

Depth-limited search

DLS fixes the infinite-branch failure by imposing a predetermined depth limit $\ell$: nodes at depth $\ell$ are treated as if they have no successors.

function DEPTH-LIMITED-SEARCH(problem, limit) returns soln / failure / cutoff

return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE), problem, limit)

 

function RECURSIVE-DLS(node, problem, limit) returns soln / failure / cutoff

if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

else if limit = 0 then return cutoff

else

cutoff_occurred? ← false

for each action in problem.ACTIONS(node.STATE) do

child ← CHILD-NODE(problem, node, action)

result ← RECURSIVE-DLS(child, problem, limit − 1)

if result = cutoff then cutoff_occurred? ← true

else if result ≠ failure then return result

if cutoff_occurred? then return cutoff else return failure

≡FactsThree possible return values

• solution - a goal was found within the limit.
• failure - there is no solution anywhere in the tree.
• cutoff - the limit was hit, so the answer is "no solution within ℓ", which is not the same thing as failure.

Criterion	DLS
Complete?	No. If the goal is deeper than ℓ, it is never found.
Time	O(b^ℓ)
Space	O(b·ℓ)
Optimal?	No.

Iterative deepening search

IDS finds the right depth limit by trying every limit: $\ell = 0, 1, 2, 3, \ldots$ until the goal turns up. It combines DFS's linear memory with BFS's completeness and optimality.

IDS re-runs a depth-limited DFS with a bigger limit each time. The shallow nodes are regenerated often, but there are very few of them.

$$N_{DLS} = b^0 + b^1 + b^2 + \cdots + b^{d-1} + b^d$$ $$N_{IDS} = (d+1)b^0 + d\,b^1 + (d-1)b^2 + \cdots + 3b^{d-2} + 2b^{d-1} + 1b^d$$

≡FactsWhy the repeated work does not matter

The shallow nodes are regenerated many times, but there are very few of them. The deep nodes, which are almost all of the nodes, are generated once or twice. The overhead is a constant factor, so IDS is still $O(b^d)$ - and that is the answer to "isn't IDS wasteful?"

Criterion	IDS
Complete?	Yes.
Time	O(bᵈ)
Space	O(b·d) - linear, like DFS.
Optimal?	Yes, with uniform step costs.

Recap

The table below is the one worth reproducing from memory.

Strategy	Frontier	Complete?	Time	Space	Optimal?
BFS	FIFO queue	yes (finite b, d)	O(bᵈ)	O(bᵈ)	yes (uniform cost)
UCS	priority queue on g	yes (step ≥ ε)	O(b^(1+⌊C*/ε⌋))	O(b^(1+⌊C*/ε⌋))	yes
DFS	LIFO stack	no	O(bᵐ)	**O(b·m)**	no
DLS	stack + limit ℓ	no	O(b^ℓ)	O(b·ℓ)	no
IDS	iterated DFS	yes	O(bᵈ)	O(b·d)	yes (uniform cost)

≡FactsThe 8-puzzle, formalised

• States - the locations of the tiles.
• Start state - the given position of the tiles.
• Goal state - the given target configuration.
• Actions - move the blank left, right, up or down.
• Cost - 1 per move.

A maze is the standard DFS problem. Note also what this definition of search deliberately excludes: games against an adversary whose moves you do not control, problems involving chance, continuous state spaces, and distributed or team control problems.