3 Informed Search

Informed Search

Recap: Search

Search problem components:

States
Actions and costs
Successor function
Start state and goal test

Search tree: nodes represent plans for reaching states; plans have costs (sum of action costs)

Search algorithm: systematically builds the search tree, chooses a node from the fringe to expand, optimal if it finds least-cost path(s)

All search algorithms differ only in how they order the fringe.

The Pancake Problem

$N$ pancakes, scrambled — want largest on bottom
You can insert a spatula at any point and flip the top portion
Goal: minimize number of flips to reach sorted order
Fun fact: studied by Bill Gates at Berkeley

Representable as a search problem. With 4 pancakes: $4! = 24$ possible states. State spaces grow exponentially. UCS on 4 pancakes opens ~25k nodes — it opens everything, but is guaranteed to find a solution.

General Tree Search

function TREE-SEARCH(problem, strategy):
    initialize tree with initial state
    loop:
        if no candidates for expansion: return failure
        choose a leaf node according to strategy
        if node is a goal state: return solution
        else: expand node, add children to tree

All search algorithms are the same algorithm with different expansion strategies:

Conceptually, all fringes are priority queues
Practically, BFS/DFS use stacks/queues to avoid log(n) overhead

Uninformed Search — Recap

Algorithm	Fringe	Complete	Optimal
DFS	LIFO stack	No	No
BFS	FIFO queue	Yes	Yes
UCS	PQ by cumulative cost g(n)	Yes	Yes

UCS weakness: explores in every direction — no information about where the goal is.

Search Heuristics

A heuristic $h(n)$ is:

An estimate of how close a state is to the goal
A function from states → values
Examples: Manhattan distance, Euclidean distance

Pancake heuristics (evaluating):

Number of pancakes out of order? ❌ too weak
Is the biggest pancake on the bottom? ❌ not enough info
Index of the largest pancake that's out of place? ✅ pretty good

Greedy Search

Expand the node with the smallest $h(n)$ — closest estimated distance to goal.

Common case: goes straight to a suboptimal goal
Worst case: behaves like a badly-guided DFS

A* Search

Combines UCS and greedy. Orders by total cost:

\[f(n) = g(n) + h(n)\]

where $g(n)$ is backward cost (path so far) and $h(n)$ is forward cost (heuristic estimate).

Algorithm	Orders by
UCS	$g(n)$ — backward cost
Greedy	$h(n)$ — forward cost
A*	$f(n) = g(n) + h(n)$ — total

Stop condition: only stop when we dequeue a goal, not when we enqueue it.

Admissible Heuristics

A is only optimal with a good heuristic. A heuristic $h(n)$ is admissible* if:

\[0 \leq h(n) \leq h^*(n)\]

where $h^*(n)$ is the true cost to the nearest goal. Admissible heuristics never overestimate — they're optimistic.

Finding good admissible heuristics is the key to A* success.

Proof: A* is Optimal with an Admissible Heuristic

Setup: Let $A$ be an optimal goal node, $B$ a suboptimal goal node.

Claim: $A$ will be expanded before $B$.

Proof:

$A$ is on the frontier, or some ancestor $n$ of $A$ is on the frontier
Show $n$ is expanded before $B$:

\[f(n) = g(n) + h(n) \leq g(A) \quad \text{(admissibility of } h \text{)}$$ $$g(A) = f(A) \quad \text{(since } h = 0 \text{ at goal)}$$ $$f(A) < f(B) \quad \text{(A is optimal, B is suboptimal)}\]

\[\therefore \quad f(n) \leq f(A) < f(B)\]

So $n$ (and thus $A$) expands before $B$. ∎

UCS vs. A*

UCS expands equally in all directions
A* expands mainly toward the goal, but hedges its bets enough to guarantee optimality

Algorithm	Orders by
UCS	\(g(n)\) — backward cost
Greedy	\(h(n)\) — forward cost
A*	\(f(n) = g(n) + h(n)\) — total