Informed Search Strategies

Source: Unit 1 §4

Informed search uses problem-specific knowledge beyond the problem definition, and that is the whole reason it beats blind search. In a graph whose nodes carry geometric coordinates, for instance, you can prefer the neighbour that is closest to the target by straight-line distance - information no uninformed strategy is allowed to look at.

Best-first search: the general framework

Best-first search selects a node using an evaluation function $f(n)$, which takes a node and returns a positive number. The node with the lowest $f(n)$ is expanded first.

◎Exam cueBest-first is UCS with a different key

The implementation is identical to uniform-cost search except that the priority queue is ordered by $f$ instead of $g$. The choice of $f$ is the strategy - greedy search and A* are the same code with two lines changed.

Most best-first algorithms build $f$ out of a heuristic function $h(n)$:

$$h(n) = \text{estimated cost of the cheapest path from } n \text{ to a goal state}$$

Heuristics are arbitrary, non-negative and problem-specific, with exactly one hard constraint.

⚠GotchaThe one rule every heuristic must obey

If $n$ is a goal node, then $h(n) = 0$. A heuristic that reports a non-zero distance at the goal breaks every optimality proof that follows.

Greedy best-first search

Greedy search expands whichever node looks closest to the goal, which means it throws away $g$ entirely:

$$f(n) = h(n)$$

The Romania example

Using $h_{SLD}$, the straight-line distance to Bucharest:

City	h_SLD	City	h_SLD
Arad	366	Rimnicu Vilcea	193
Timisoara	329	Fagaras	176
Zerind	374	Bucharest	0
Sibiu	253	Oradea	380

Greedy best-first jumps to whichever city looks closest to Bucharest. It gets there, but the route through Rimnicu Vilcea and Pitesti is 32 km shorter.

⚠GotchaTwo ways greedy search fails

• Not optimal. For Arad → Bucharest it expands no off-path node at all, which is a wonderful search cost, but the Sibiu → Fagaras route is 32 km longer than the route through Rimnicu Vilcea and Pitesti. At each step it grabs the node that looks closest.
• Not complete, even in a finite space, exactly like DFS. Going from Iasi to Fagaras, the heuristic recommends Neamt, a dead end; expanding Neamt puts Iasi back on the frontier, Iasi still looks closer than Vaslui, and the search loops forever.

Criterion	Greedy best-first
Complete?	No, it can get stuck in loops.
Time	O(bᵐ), though a good heuristic improves this dramatically.
Space	O(bᵐ), it keeps all nodes in memory.
Optimal?	No.

A* search

The most widely known best-first search, and the one to know cold. A* adds the cost already paid to the cost still estimated:

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

A* scores each node by the whole journey: what the path has already cost plus what the heuristic thinks is left.

≡FactsReading the three terms

• $g(n)$ - the path cost from start to $n$, which is known and actual.
• $h(n)$ - the estimated cost from $n$ to the goal.
• $f(n)$ - the estimated cost of the cheapest solution through $n$.

The algorithm is UCS with the queue ordered by $g + h$. Provided $h$ meets the conditions below, A* is both complete and optimal.

Condition 1: admissibility

An admissible heuristic never overestimates the cost to reach the goal. Since $g(n)$ is the true cost to $n$, an admissible $h$ means $f(n)$ never overestimates the true cost of a solution through $n$. Admissible heuristics are optimistic: they believe the goal is closer than it really is.

Straight-line distance is the model example. The shortest path between two points is a straight line, so $h_{SLD}$ can never overestimate.

≡FactsWhich condition applies where

• Admissibility is what you need for tree search to be optimal.
• Consistency is what you need for graph search to be optimal.

Condition 2: consistency (monotonicity)

A heuristic is consistent if, for every node $n$ and every successor $n'$ reached by action $a$:

$$h(n) \le c(n, a, n') + h(n')$$

Consistency is the triangle inequality applied to n, its successor n′, and the goal.

◎Exam cueThe implication runs one way only

Consistency ⇒ admissibility. Consistency is the stricter requirement, so every consistent heuristic is admissible, and the converse is not true.

A* worked through

Label each node (name, g, f) where $f = g + h$. Expand the lowest $f$ first, and goal-test on pop.

Frontier ordered by f:

S(0,5) → expand → A(7,12), B(3,11), D(6,12)

pop B(3,11) → generates C(4,12), E(5,13) …

continue popping the smallest f until a GOAL node is popped.

A* balances the cost already spent, $g$, against the cost estimated as remaining, $h$. Note that A is reached with $g = 7$ but scores $f = 12$, the same as D at $g = 6$: a cheap path so far and a pessimistic heuristic can tie with an expensive path and an optimistic one, which is exactly the trade the sum is there to make.

Criterion	A*
Complete?	Yes, unless there are infinitely many nodes with f ≤ f(G).
Time	Exponential in general.
Space	Keeps all nodes in memory, which is the practical bottleneck.
Optimal?	Yes, with an admissible (tree) or consistent (graph) heuristic.

The heuristic is the controller

Everything about A*'s efficiency is decided by the choice of $h$.

≡FactsHow h changes the search

• $h \equiv 0$ is admissible, and reduces A* to UCS. Correct, and usually inefficient.
• The higher $h$ is while staying admissible, the fewer nodes A expands.* More informed means less searching, so push $h$ up to the admissibility ceiling.
• 8-puzzle, weak heuristic: $h(n) = W(n)$, the number of misplaced tiles. Admissible, but a poor estimate.
• 8-puzzle, better heuristic: $h(n) = P(n)$, the sum of the Manhattan distances of the tiles from home, ignoring the other tiles.

⚠GotchaAccuracy is not free

A more accurate heuristic prunes more nodes but costs more to compute per node. The right $h$ is the one that minimises total time, not the one that minimises expansions.

✓Best practiceWeighted A* when good enough beats optimal

Use $f = g + w \cdot h$ with $w > 0$. A large $w$ over-weights the heuristic and makes the search greedier and faster; a small $w$ gives it a more breadth-first character. In games you usually want a good path now rather than the best path later, so slightly inflating $h$ - a base cost of 1.5 instead of 1, say - stops A* obsessing over marginally cheaper terrain.

Choosing a heuristic on a grid

Grid and movement	Recommended heuristic
Square grid, 4 directions	Manhattan distance (L1)
Square grid, 8 directions	Diagonal distance (L∞)
Square grid, any direction	Euclidean distance (L2)
Hexagonal grid, 6 directions	Manhattan adapted to hex grids
Multiple goals	h′(x) = min(h₁(x), h₂(x), h₃(x), …)