Class Notes

Lab 02

Informed Search

Greedy Beam Hill Climbing A*
Work in progress These notes are still being written and reviewed: content may change, and some parts may still contain mistakes.

Uninformed vs. Informed Search

  • Uninformed Search: uninformed strategies use only the information available in the problem definition (see Lab 01).
  • Informed Search: informed strategies have information on the goal state, which helps in more efficient searching. This information is obtained by a function (heuristic) that estimates how close a state is to the goal state.

Informed Search Strategies

Heuristic

📐 Definition

A heuristic h(n) is a function that estimates the cost (or distance) from a given state n to a goal state.

  • The computation performed by such a function is specific to the search problem being solved.

A concrete example — two heuristics for the 8-puzzle — follows in Choosing a heuristic.

Greedy

Greedy Search

Description: Greedy search is a strategy for exploration that always selects the frontier node with the lowest heuristic value for expansion, which corresponds to the state it believes is nearest to a goal.

Frontier Representation: Greedy search operates identically to UCS, with a priority queue — but the priority is the heuristic h(n) instead of the path cost.

Complete?
No
But complete in finite space with repeated-state checking.
Optimal?
No
Time complexity
O(bm)
A misleading "bad" heuristic may lead us to possibly explore all nodes.
Space complexity
O(bm)
Keeps all nodes in memory.
Data structure
Priority queue (by h(n))

Greedy search is not guaranteed to find a goal state if one exists, nor is it optimal, particularly in cases where a very bad heuristic function is selected. It generally acts fairly unpredictably from scenario to scenario, and can range from going straight to a goal state to acting like a badly-guided DFS and exploring all the wrong areas.

Step through greedy search on the graph below — h(n) is printed under each node, edge costs on the arrows. Greedy follows the lowest h and reaches G via S → C → F → G with cost 26, even though S → A → D → F → G costs only 23: it never looks at the cost already paid.

Frontier
Search log
Beam

Beam Search (Local Beam Search)

= greedy best-first search with queue limit l, i.e., keeps only the l best nodes in the queue.

Complete?
No
It is a local search — the goal can be pruned away.
Optimal?
No
Time complexity
O(bml)
l nodes × b successors, repeated for m levels.
Space complexity
O(bl)
Linear space.
Data structure
Limited priority queue (size l, by h(n))

Why O(bml) time?

At every level the algorithm does the following:

  • Expansion: the algorithm only expands the l nodes selected from the previous level.
  • Generation of Successors: each of the l nodes generates b successors (children). The total number of new candidates generated at this level is l × b.
  • Heuristic Evaluation / Scoring: the algorithm calculates the score h(n) for all l · b candidates. This step takes time proportional to O(l · b).
  • Pruning (Selection): the algorithm selects the best l candidates out of the l · b total to carry forward to the next level. Sorting or selection takes time, often O(l · b log(l · b)) if sorting is done, or faster if efficient selection algorithms (like Quickselect or a min-heap) are used. In many common search contexts, this selection step is often simplified or amortized, or assumed to be minor compared to the expansion cost, leading to the linear complexity.

Overall time complexity: since the process is repeated for m levels, the total time complexity is O(m · l · b).

Step through beam search on the same graph and change the beam width l. Every time the frontier grows beyond l nodes, the worst ones (highest h) are thrown away for good — there is no going back to them.

2
Frontier
Search log
Hill Climbing

Hill Climbing

= greedy best-first search with queue limit l = 1, i.e., keeps only the best node. In other words, it is beam search with a beam of width 1.

Complete?
No
Optimal?
No
Time complexity
O(bm)
Beam search's O(bml) with l = 1.
Space complexity
O(b)
Beam search's O(bl) with l = 1.
Data structure
Limited priority queue (size 1)

Random-restart hill climbing overcomes local maxima — trivially complete.

Step through hill climbing on the same graph. After each expansion only the single best child survives; everything else is discarded and there is no backtracking.

Frontier
Search log

Local maxima & random restarts

Seen as optimization, hill climbing keeps moving to the better neighbour until no neighbour is better. On the landscape below that often means getting stuck on a local maximum. Random restart simply climbs again from a new random state and keeps the best result — with enough restarts, it will eventually start on the slope of the global maximum.

0
climbs (restarts)
–
last climb stopped at
–
best found so far

Click “Random start & climb”. The global maximum is marked with a dashed line.

A*

A* and optimality of A*

Idea: avoid expanding paths that are already expensive.

  • Evaluation function f(n) = g(n) + h(n)
    • g(n) = cost so far to reach n
    • h(n) = estimated cost from n to goal
    • f(n) = estimated total cost of path through n to goal

Admissible heuristic: A* requires it

  • A heuristic is admissible if h(n) ≤ h*(n) for every node n
  • h*(n) is the true cost of the cheapest path from n to a goal
  • So h(n) never overestimates the cost to reach a goal
  • We also require h(n) ≥ 0. For a goal G:

h*(G) = 0 0 ≤ h(G) ≤ h*(G) = 0 hence h(G) = 0.

n A G 4 5 h(n) = 7 h*(n) = 4 + 5 = 9
Frontier
Search log
Complete?
Yes
Optimal?
Yes
Cannot expand fi+1 until fi is finished.
Time complexity
O(bd)
Space complexity
O(bd)
Data structure
Priority queue (by f(n) = g(n) + h(n))

Let C* be the cost of the optimal solution:

  • A* expands all nodes with f(n) < C*
  • A* expands some nodes with f(n) = C*
  • A* expands no nodes with f(n) > C*

Theorem: A* Search is Optimal

  • If h(n) is admissible, A* using TREE-SEARCH is optimal.
  • If h(n) is consistent, A* using GRAPH-SEARCH is optimal.
    • Optimality: a consistent heuristic guarantees that once a node is expanded, its cost will not be improved upon. Thus, the path found by A* will be the shortest possible.
    • Efficiency: because consistent heuristics prevent the re-expansion of nodes, they help reduce unnecessary evaluations, leading to a more efficient search process.

If h(n) is consistent, then it is also admissible; however, the converse is not necessarily true.

Proof (admissible h, tree search)

Suppose some suboptimal goal G2 has been generated and is in the queue. Let n be an unexpanded node on a shortest path to an optimal goal G1.

Start n G₁ G₂ optimal goal suboptimal goal
1
f(G2) = g(G2) — the actual path to G2, since h(G2) = 0
2
f(G2) > g(G1) — since G2 is suboptimal
3
f(G2) > g(G1) ≥ f(n) = g(n) + h(n) — since h is admissible
⇒
Since f(G2) > f(n), A* will never select G2 for expansion.

Lemma: A* expands nodes in order of increasing f value

  • A heuristic is consistent if h(n) ≤ c(n, a, n′) + h(n′)
  • If h is consistent, we have:

f(n′) = g(n′) + h(n′) = g(n) + c(n, a, n′) + h(n′) ≥ g(n) + h(n) = f(n) hence f(n) is nondecreasing along any path.

n n′ G c(n,a,n′) h(n) h(n′)

Admissible vs. consistent heuristics

To summarize, a heuristic is:

📐 Admissible

h(n) ≤ h*(n) for all n, where h*(n) is the true cost from n to the goal state — it never overestimates.

📐 Consistent

h(n) ≤ c(n, n′) + h(n′) for all n and every successor n′ — the heuristic can drop by at most the step cost.

  • Rearranging this gives the key insight that the drop in the heuristic value must be less than or equal to the actual move cost: h(n) − h(n′) ≤ cost(n, n′).
  • Proof strategy for consistency: to prove consistency, you must check the inequality for every possible single step from any node n to its neighbor n′. This usually involves showing that the move action is constrained such that the heuristic can decrease by at most the step cost.
❗ Key relationship

Consistent⟹Admissible

Any consistent heuristic is also admissible (assuming h(G) = 0). Proving consistency is sufficient to prove admissibility.

Not the other way round: an admissible heuristic can be inconsistent (example below).

Example: admissible, but not consistent

Is A* with graph search always guaranteed to find the optimal solution when using an admissible heuristic?

1 3 1 2 S A B C h(S)=4 h(A)=3 h(B)=0 h(C)=0

The heuristic h is admissible — h(n) ≤ h*(n), true cost to goal C

S
h(S) = 4 ≤ 4 = 1+1+2
admissible
A
h(A) = 3 ≤ 3 = 1+2
admissible
B
h(B) = 0 ≤ 2
admissible
C
h(C) = 0 ≤ 0
admissible

But not consistent — h(n) ≤ c(n, n′) + h(n′) fails

S → A
h(S) = 4 ≤ 1 + 3 = 4
consistent
S → B
h(S) = 4 > 3 + 0 = 3
inconsistent
A → B
h(A) = 3 > 1 + 0 = 1
inconsistent
B → C
h(B) = 0 ≤ 2 + 0 = 2
consistent

The optimal path from S to C is S–A–B–C with a total cost of 4. However, with A* graph search:

  • After starting from S, the options on the frontier are S–A with a cost plus heuristic of 1 + 3 = 4, or S–B with a cost plus heuristic of 3 + 0 = 3. So, we choose to explore S–B.
  • Next, the options on the frontier are S–A with f = 1 + 3 = 4, or B–C with a backward path cost of 5. So, we choose to explore S–A.
  • We've already reached B from the earlier path, so we don't consider edge A–B. Thus, our only option is to explore B–C for a cost of 5.
  • So, we will choose the path S–B–C with a total cost of 5, which is not optimal.

Tree Search

  • In tree search, a closed set is not needed because nodes are not revisited; there's no way to reach the same node via multiple paths.
  • The heuristic must be admissible, ensuring that A* will find the optimal path.

Graph Search

  • The heuristic must be both admissible and consistent to guarantee that A* finds the optimal path efficiently.
  • A consistent heuristic guarantees an optimal path even without a closed set, but reprocessing nodes can be inefficient.
  • An inconsistent heuristic can cause extra node expansions, and with a closed set it can even return a suboptimal solution.

Choosing a heuristic

E.g., for the 8-puzzle:

  • h1(n) = number of misplaced tiles (Hamming distance)
  • h2(n) = total Manhattan distance (i.e., no. of squares from desired location of each tile)
    • cellDist = |x − x′| + |y − y′|

Current state

Goal state

Click a tile next to the blank to slide it (one move, cost 1).

–
h₁ — misplaced tiles (Hamming)
–
h₂ — Manhattan distance
0
moves made

No move yet.

h1(S) = 1 + 0 + 1 + 1 + 1 + 0 + 1 + 1 = 6 h2(S) = 4 + 0 + 3 + 3 + 1 + 0 + 2 + 1 = 14

  • Both Manhattan and Hamming heuristics are admissible and consistent.

Dominance: the larger admissible heuristic is better

  • If h2(n) ≥ h1(n) for all n (both admissible), then h2 dominates h1 and is better for search.
  • Given any admissible heuristics ha and hb, then h(n) = max(ha(n), hb(n)) is admissible and dominates ha, hb:

ha(n) ≤ h*(n) and hb(n) ≤ h*(n) ⇒ max(ha(n), hb(n)) ≤ h*(n) hence max(ha, hb) is admissible, and it is ≥ both.

cost 0 better h₁(S) = 6 misplaced h₂(S) = 14 Manhattan h*(S) = 20 true cost 8-puzzle start S from above

More formally: the Manhattan distance

The Manhattan distance heuristic, hM(n), is the sum of the horizontal and vertical distances of every misplaced tile from its goal position.

📐 Manhattan distance

hM(n) = Σall tiles |current row − goal row| + |current column − goal column|

Admissibility proof for Manhattan distance

Relaxed problem: a tile can be moved to its goal position in one step, regardless of what other tiles or the blank space are doing.

  1. The true cost, h*(n), is the number of moves needed to move all tiles to their correct positions without collisions.
  2. The Manhattan distance hM(n) calculates the minimum number of unit steps required for each tile individually to reach its goal position, ignoring the presence of other tiles and the constraint of the blank space.
  3. Since the true problem requires a tile to wait for the blank space and potentially move other tiles out of the way, the actual number of moves h*(n) must be greater than or equal to the total minimum unit steps of all tiles.
  4. Therefore, hM(n) is a lower bound on h*(n):

hM(n) ≤ h*(n)

Consistency proof for Manhattan distance

Assume a move from node n to n′ by sliding the blank tile, which swaps positions with an adjacent tile, T. The step cost is cost(n, n′) = 1.

  1. The heuristic value hM(n) changes only for the tile T that was moved. All other tiles' distances remain the same.
  2. Since tile T was adjacent to the blank space, it moved one step closer to or one step farther from its goal position.
  3. Best case: if the move brings tile T one step closer to its goal, the Manhattan distance for T decreases by 1. ΔhM = −1 ⟹ hM(n) − hM(n′) = 1
  4. Worst case: if the move takes tile T one step farther from its goal, the Manhattan distance for T increases by 1. ΔhM = +1 ⟹ hM(n) − hM(n′) = −1

In all cases, the change in the heuristic value hM(n) − hM(n′) is ≤ 1. Since cost(n, n′) = 1, the consistency inequality is satisfied: hM(n) − hM(n′) ≤ 1 = cost(n, n′).

hM(n) ≤ cost(n, n′) + hM(n′)

You can check this in the puzzle above: every slide changes h₂ by exactly ±1.

Memory-Bounded A*

📐 Definition

= combination between A* and beam search, i.e., keeps only l nodes in the queue.

IDA*

IDA* — Iterative Deepening A*

= combination between A* and iterative deepening search, i.e., uses the A* evaluation function f(n) = g(n) + h(n) as a threshold and runs DLS.

  • Each iteration is a depth-first search that prunes every node with f(n) > threshold.
  • The next threshold is the smallest f-value that was pruned in the previous iteration.
Complete?
Yes
Optimal?
Yes
Time complexity
O(bd)
Space complexity
O(bd)
It's a DFS underneath.
Data structure
Stack

Example of the IDA* algorithm

In the tree below, the f score is written inside each node (it is already computed). The start node is 2 and the goal node is 15. Nodes visited in the current iteration are coloured green.

visited this iteration pruned (f > threshold) goal

Iteration 1 — threshold = 2

Threshold = 2 Pruned: 4, 5 Start 2 4 5 5 4 6 6 7 8 8 7 6 8 7 9 12 14 16 15 12 9 13 8 13 7 15 16 8 14 16 10 Goal
  • Root node as current node, i.e. 2.
  • Threshold = current node value (2 = 2). So explore its children.
  • 4 > threshold & 5 > threshold. So, this iteration is over and the pruned values are 4 and 5.

Iteration 2 — threshold = 4

Threshold = 4 Pruned: 5, 8, 7, 5 Start 2 4 5 5 4 6 6 7 8 8 7 6 8 7 9 12 14 16 15 12 9 13 8 13 7 15 16 8 14 16 10 Goal
  • In pruned values, the least is 4, so threshold = 4.
  • Current node = 2 and 2 < threshold, so explore its children one by one.
  • First child 4: set current node = 4, equal to the threshold, so explore its children 5 and 4. 5 > threshold, so prune it; the second child 4 = threshold, so explore its children 8 & 7 — both > threshold, so prune them.
  • Similarly, explore the second child of the root, 5: 5 > threshold, so prune it.
  • So, our pruned values are 5, 8, 7 (and 5).

Iteration 3 — threshold = 5

Threshold = 5 Pruned: 7, 8, 8, 7, 6, 6 Start 2 4 5 5 4 6 6 7 8 8 7 6 8 7 9 12 14 16 15 12 9 13 8 13 7 15 16 8 14 16 10 Goal
  • In pruned values, the least is 5, so threshold = 5.
  • Current node = root = 2 < threshold, so explore its children one by one.
  • First child 4 < threshold: explore its children 5 and 4. 5 = threshold, so explore its children 7 & 8 — both > threshold, pruned. The second child 4 < threshold: explore its children 8 & 7 — both > threshold, pruned. Pruned so far: 7 & 8.
  • Explore the second child of the root, 5 = threshold, so explore its children 6 & 6 — both > threshold, pruned.
  • So, our pruned values are 7, 8 & 6.

Iteration 4 — threshold = 6

Threshold = 6 Pruned: 7, 8, 8, 7, 13, 7, 8, 7, 9 Start 2 4 5 5 4 6 6 7 8 8 7 6 8 7 9 12 14 16 15 12 9 13 8 13 7 15 16 8 14 16 10 Goal
  • In pruned values, the least is 6, so threshold = 6.
  • Left subtree as before: 4 → 5 → 7 & 8 pruned; 4 → 8 & 7 pruned. Pruned so far: 7 & 8.
  • Second child of the root, 5 < threshold: explore its children 6 & 6, both = threshold, so explore them one by one.
  • The first 6 has children 6 & 8. 6 = threshold, so explore its children 13 & 7 — both > threshold, pruned. 8 > threshold, pruned. Pruned at this stage: 13, 7 & 8.
  • The second 6 = threshold: explore its children 7 & 9 — both > threshold, pruned.
  • So, our pruned values are 13, 7, 8 & 9.

Iteration 5 — threshold = 7

Threshold = 7 Pruned: 12, 14, 8, 8, 13, 8, 13, 8, 8, 14, 9 Start 2 4 5 5 4 6 6 7 8 8 7 6 8 7 9 12 14 16 15 12 9 13 8 13 7 15 16 8 14 16 10 Goal
  • In pruned values, the least is 7, so threshold = 7.
  • First child 4 < threshold: its first child 5 < threshold, explore 7 & 8. 7 = threshold, so explore its children 12 & 14 — both > threshold, pruned. 8 > threshold, pruned.
  • Second child of 4, i.e. 4 < threshold: children 8 & 7. 8 > threshold, pruned; 7 = threshold, so explore its children 13 & 8 — both > threshold, pruned. Pruned so far: 12, 14, 8 & 13.
  • Second child of the root, 5 < threshold: explore 6 & 6. The first 6 has children 6 & 8; 6 < threshold, explore its children 13 & 7: 13 > threshold, pruned; 7 = threshold and it has no children. Then 8 > threshold, pruned.
  • The second 6 < threshold: explore 7 & 9. 7 = threshold, so explore its children 8 & 14 — both > threshold, pruned. 9 > threshold, pruned.
  • So, our pruned values are 12, 14, 8, 13 & 9.

Iteration 6 — threshold = 8

Threshold = 8 Goal found Start 2 4 5 5 4 6 6 7 8 8 7 6 8 7 9 12 14 16 15 12 9 13 8 13 7 15 16 8 14 16 10 found
  • In pruned values, the least is 8, so threshold = 8.
  • Left subtree: 4 → 5 → 7 < threshold, explore 12 & 14 — pruned. 8 = threshold, explore 16 & 15 — pruned. Pruned so far: 12, 14, 16 & 15.
  • 4 → 8 = threshold, explore 12 & 9 — pruned. 7 < threshold, explore 13 & 8: 13 pruned; 8 = threshold and it has no children. Pruned so far: 12, 14, 16, 15, 9 and 13.
  • Second child of the root, 5 < threshold: explore 6 & 6 one by one. The first 6 has children 6 & 8; 6 < threshold, explore 13 & 7: 13 pruned, 7 < threshold with no children.
  • Next sub-child of 6 is 8 = threshold, so explore its children: 15 is the goal — found! The search stops; the second 6 is never visited.

Note on the goal test: in this example the goal is reported as soon as it is generated (as a child of the f = 8 node at threshold 8). Textbook IDA* applies the goal test when a node is expanded, which requires f(goal) = 15 ≤ threshold — so it would keep iterating until the threshold reaches 15. You can compare both in the interactive version below.

Step through IDA* yourself

Threshold = 2
current visited this iteration pruned goal
Pruned f-values (this iteration)
Search log

Example adapted from GeeksforGeeks — Iterative Deepening A* algorithm (IDA*).

Simulated Annealing

Simulated annealing escapes local maxima the opposite way hill climbing gets stuck: it allows some "bad" moves, accepted with probability exp(−Δ/T), and gradually cools T so bad moves become rarer over time.

–
P(accept worse move) = exp(−Δ/T)

High T, small Δ → almost always accept (explore). Low T, large Δ → almost never accept (settle). As T → 0 over time, this converges to hill climbing. Watch: simulated annealing

Reference

Summary of algorithms

AlgorithmCompleteOptimalTimeSpaceData structure
GreedyNo*NoO(b^m)O(b^m)Priority queue
Beam SearchNoNoO(bml)O(bl)Limited priority queue
Hill ClimbingNoNoO(bm)O(b)"Limited priority queue"
A*Yes*YesO(b^d)O(b^d)Priority queue
IDA*YesYesO(b^d)O(bd)Stack

Same algorithms, real papers

Research connections

These algorithms aren't just puzzle-solvers. Same three ingredients every time — search node, action, frontier/heuristic — applied to proofs, prompts and learned heuristics instead of grids.

Greedy / Best-First

LeanDojo: Theorem Proving with Retrieval-Augmented Language Models

Yang et al. · NeurIPS 2023 · arXiv:2306.15626
Core idea
ReProver is a theorem-prover LM: it repeatedly proposes the next proof "tactic," retrieving relevant lemmas from a huge math library to help decide.
Problem
Prior LLM theorem provers were unreproducible and bad at picking the right lemma from a large library.
How the algorithm fits
Search leaves grid-world entirely: a proof state is the search node, a tactic is the action, and best-first search explores the proof tree, expanding the state with the highest cumulative probability of its proof so far. Search isn't just for route planning.
Read the deep dive — with an interactive proof-search tree →

Hill Climbing / Local Search

Plum: Prompt Learning using Metaheuristic

Pan et al. · ACL Findings 2024 · 2024.findings-acl.129
Core idea
Finding a good LLM prompt is a search over a huge space of text strings. Plum tries six classic metaheuristics — including hill climbing and simulated annealing — to find human-readable prompts.
Problem
Prompt optimizers need to be automatic, discrete, black-box, gradient-free, and interpretable — most methods only hit some of these.
How the algorithm fits
A prompt is the search node; an LLM-based edit is the action; task accuracy is the heuristic/fitness. Hill climbing accepts a neighbor only if it scores higher, stopping when no neighbor improves.

A*

Learning Admissible Heuristics for A*: Theory and Practice

Futuhi, Sturtevant · ICLR 2026 · arXiv:2509.22626
Core idea
Neural heuristics are powerful but usually aren't trained to respect admissibility. This paper's Cross-Entropy Admissibility (CEA) loss explicitly trains a network to stay admissible, with proven sample-complexity bounds for generalizing to new instances.
Problem
Learned heuristics can overestimate true cost, silently breaking A*'s optimality guarantee, with no guarantee they'll work on unseen problems.
How the algorithm fits
Directly next to this lecture: h(n) is a neural net trained to satisfy h(n) ≤ h*(n), which is exactly the condition that keeps A* optimal. Evaluated on Rubik's Cube against pattern-database heuristics.
Test yourselfLab 02 quiz

19 auto-graded tasks, 100 points: g / h / f, greedy, beam search, hill climbing, simulated annealing, tracing A*, admissible and consistent heuristics, IDA*, and choosing an algorithm.

Start the quiz →