Informed Search and Heuristic Design #
Informed search uses additional knowledge to estimate which states are most promising. A good heuristic can greatly reduce unnecessary exploration while preserving solution quality.
Learning Objectives #
- explain the purpose of a heuristic function
- compare Greedy Best-First Search and A* Search
- test heuristics for admissibility and consistency
- explain heuristic dominance and effective branching factor
- derive heuristics from relaxed problems and subproblems
- describe pattern databases, landmarks and learned heuristics
1. What Is Informed Search? ☆ #
Uninformed search knows only how to generate successors and recognise a goal. Informed search additionally estimates whether one non-goal state is more promising than another.
A heuristic is a practical estimate that guides search towards a goal.The heuristic function is written as \( h(n) \) and estimates the remaining cost from node \( n \) to a goal.
A heuristic is like a compass in a maze. It does not necessarily reveal the exact route, but it helps the search choose a promising direction.
2. Greedy Best-First Search ☆ #
Greedy Best-First Search (GBFS) expands the node that appears closest to the goal.
\[ f(n) = h(n) \]It ignores the cost already paid to reach the node. This can make it fast, but a promising-looking state may lie on an expensive route. GBFS therefore does not generally guarantee an optimal solution.
3. A* Search ☆ #
A Search* combines the actual cost so far with the estimated remaining cost.
\[ f(n) = g(n) + h(n) \]where:
- \( g(n) \) is the actual path cost from the start to \( n \)
- \( h(n) \) is the estimated cost from \( n \) to the goal
- \( f(n) \) is the estimated total cost of a solution through \( n \)
At each step, A* expands the frontier node with the smallest \( f(n) \) .
| Algorithm | Evaluation | Behaviour |
|---|---|---|
| UCS | \( g(n) \) | Cheapest path so far |
| GBFS | \( h(n) \) | Apparently closest to goal |
| A* | \( g(n)+h(n) \) | Balances travelled and remaining cost |
4. Admissible Heuristics ☆ #
A heuristic is admissible if it never overestimates the true remaining cost.
\[ 0 \leq h(n) \leq h^{*}(n) \]Here, \( h^{*}(n) \) is the actual cheapest cost from \( n \) to a goal.
An admissible heuristic is optimistic: it may underestimate, but it does not exaggerate. Straight-line distance is an admissible estimate of road distance because a road route cannot be shorter than the direct geometric distance.
5. Consistent Heuristics ☆ #
A heuristic is consistent if its estimate obeys a triangle-like condition across every transition:
\[ h(n) \leq c(n,a,n') + h(n') \]The estimate at a node must not exceed the step cost to a successor plus the successor’s estimate.
Consistency ensures that \( f(n) \) values do not decrease along a path. For graph search, this means that once A* expands a node, the cheapest path to that node has already been found.
Every consistent heuristic with \( h(Goal)=0 \) is admissible, but an admissible heuristic need not always be consistent.
6. What Makes a Good Heuristic? #
A useful heuristic should be:
- accurate — close to the true remaining cost
- fast to compute — guidance should not cost more than the search it saves
- admissible — when optimal A* search is required
- consistent — to avoid decreasing estimates along paths
- informative — able to distinguish promising states
Heuristic dominance #
Suppose \( h_1 \) and \( h_2 \) are admissible and:
\[ h_2(n) \geq h_1(n) \]for every node. Then \( h_2 \) dominates \( h_1 \) because it is closer to the true cost without overestimating. A* using \( h_2 \) will usually expand no more nodes than A* using \( h_1 \) .
If \( h(n)=0 \) for every node, A* behaves like UCS.
7. Effective Branching Factor #
The effective branching factor measures how strongly a heuristic reduces the apparent width of a search tree.
If A* generates \( N+1 \) nodes to find a solution at depth \( d \) , then \( b^{*} \) satisfies:
\[ N+1 = 1+b^{*}+(b^{*})^2+\cdots +(b^{*})^d \]A smaller \( b^{*} \) indicates better guidance and fewer generated nodes.
8. Heuristics from Relaxed Problems ☆ #
A relaxed problem removes one or more constraints from the original problem, making it easier to solve.
The optimal cost of the relaxed problem is a lower bound on the original cost because removing restrictions cannot make the problem harder. It can therefore provide an admissible heuristic.
8-puzzle example #
| Relaxation | Resulting heuristic |
|---|---|
| A tile may move to any position | Number of misplaced tiles |
| Tiles may move through one another | Sum of Manhattan distances |
Manhattan distance is usually more informative because it accounts for how far each tile is from its goal position.
Relax the rules, solve the easier problem, and use that solution cost as a lower-bound estimate for the original problem.
9. Pattern Databases ☆ #
A pattern database stores exact solution costs for abstracted subproblems.
For a sliding-tile puzzle, it may precompute the optimal cost for configurations involving only a selected group of tiles. During search, the algorithm looks up the matching abstract pattern and uses its stored cost as a heuristic.
Pattern databases exchange preparation time and storage for faster search later.
10. Landmarks #
A landmark heuristic precomputes distances involving selected important states. In a road network, landmarks might be major cities or interchanges. These known distances help estimate the cost between a current location and a destination without solving every route from scratch.
11. Learning Heuristics from Experience #
Instead of designing every heuristic manually, a model can learn to predict remaining cost from previously solved problems.
Examples include:
- learning which features predict expensive or unproductive states
- training a neural network to produce \( h(s;\theta) \)
- using learned estimates inside A* or GBFS
For grid-based problems such as Sokoban, mazes with teleports and sliding-tile puzzles, a neural network can process the grid and output one predicted heuristic value.
A learned heuristic may guide search well without being admissible. Prediction accuracy and the guarantees required by A* are separate considerations.
Common Mistakes #
\( h(n) \)
estimates the cost from the current node to the goal; ( g(n) )
is the cost already paid.
- GBFS uses only ( h(n) )
; A* uses both ( g(n) )
and ( h(n) )
.
- An admissible heuristic need not be exact; it only must not overestimate.
- The most accurate heuristic is not automatically best if it is extremely expensive to compute.
- A relaxed problem removes constraints; it does not add new restrictions.
Practice Questions #
- Explain the different roles of \( g(n) \) , \( h(n) \) and \( f(n) \) in A*.
- Why can GBFS reach a non-optimal solution?
- Test whether a given heuristic is admissible.
- Test consistency across an edge with cost \( c(n,a,n') \) .
- Why does a relaxed problem produce a lower bound?
- Compare misplaced tiles with Manhattan distance for the 8-puzzle.
- What does a pattern database store?
- Why can a more informative heuristic reduce the effective branching factor?
Key Takeaways #
- GBFS chooses by estimated remaining cost; A* combines actual and estimated cost.
- Admissibility prevents overestimation, while consistency constrains estimates across neighbouring states.
- A more informative admissible heuristic normally allows A* to expand fewer nodes.
- Relaxed problems, pattern databases, landmarks and experience can all produce useful heuristics.
- Learned heuristics can improve guidance, but their optimality guarantees must be checked separately.
Checklist #
- I can calculate \( f(n)=g(n)+h(n) \) .
- I can distinguish GBFS, UCS and A*.
- I can test admissibility and consistency.
- I can explain heuristic dominance and effective branching factor.
- I can derive a heuristic from a relaxed problem.
- I can explain pattern databases and learned heuristics.