A* Nuances and Local Search in AI: Hill Climbing, Random Restart & Beam Search

In my previous post on AI search algorithms, I wrote about how BFS, DFS, Uniform Cost Search, Greedy Search, and A* all follow the same loop: pull a state from the frontier, check if it’s the goal, and push its neighbors back onto the frontier.

In our third lecture of Intro to AI at USF, we wrapped up the subtler details of A* Search (like when it is actually safe to stop searching, how to compare two good heuristics, and how Weighted A* bends the rules for speed) before flipping the problem on its head with Local Search.

I built the interactive visualizer below so you can run and compare Standard A*, Weighted A*, Hill Climbing (including watching it get trapped at a local maximum), Random-Restart Hill Climbing, and Beam Search (k = 2) right inside the page.

Interactive Visualizer: Weighted A*, Hill Climbing & Beam Search

Select any algorithm below and press Play, Step, or Show Result (or click any row in the comparison table) to see how it behaves on the graph. Pay special attention to what happens at node A (score = 68, a local peak whose immediate child C drops to score = 55) when you run Hill Climbing versus Random-Restart or Beam Search (k = 2).

Part 1: Finishing A* Search (The Details That Actually Matter)

A* evaluates every frontier node by combining the cost already spent (g(n)) with the estimated cost remaining (h(n)):

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

That formula is simple enough, but there were four subtleties from our Day 3 lecture that made a huge difference in how I understand A* in practice.

1. The Stopping Rule: Don’t Stop When Goal Enters the Frontier

When you run BFS, you can often stop the moment you generate a goal node. With A* (and Uniform Cost Search), stopping as soon as the goal is added to the frontier is a bug.

Goal enters frontier          -> DO NOT STOP YET
Goal is popped with lowest f  -> Safe to return optimal solution

Why? Because the first path that spots the goal might have a high edge cost (say f(G) = 12), while another node sitting on the frontier has f = 8 and is one cheap step away from reaching G with a total cost of 9. You only know you have the cheapest path when G itself is popped from the priority queue with the lowest f(n) score.

2. Choosing a Heuristic: Manhattan vs. Euclidean Distance

In grid and map problems, your choice of heuristic h(n) depends on how the agent is allowed to move:

• Euclidean distance (straight-line): Best when you can move at any angle (“as the crow flies”).
• Manhattan distance (|dx| + |dy|): Best when movement is restricted to 4 directions (North, South, East, West), like walking along city blocks.

If a goal is 4 blocks East and 3 blocks North:

• Euclidean distance is 5 (sqrt(4^2 + 3^2)).
• Manhattan distance is 4 + 3 = 7.

If you cannot move diagonally, both heuristics are admissible (neither overestimates the true 7-step walk), which leads directly to the next question: which one is better?

3. Heuristic Dominance: Why Bigger (Safe) Estimates Win

Suppose two heuristics h1 and h2 are both admissible (h(n) <= h*(n)), and for every node:

h2(n) >= h1(n)

We say that h2 dominates h1. Because h2 is closer to the true remaining cost without going over, it gives A* a tighter estimate and forces A* to expand fewer wasted nodes.

Even better, if you have two or more admissible heuristics (even if neither dominates the other everywhere), you can combine them into a single, stronger admissible heuristic by taking their maximum at every state:

h(n) = max(h1(n), h2(n), ...)

Since neither h1 nor h2 ever overestimates the true cost, the larger of the two still never overestimates the true cost!

4. Weighted A*: Trading Strict Optimality for Speed

What if a state space is so huge that standard A* still expands too many nodes? Weighted A* multiplies the heuristic by a weight W > 1:

f(n) = g(n) + W * h(n)

Think of W as a dial that slides between all the algorithms we’ve learned:

• W = 0: Ignores h(n) completely -> Uniform Cost Search (UCS)
• W = 1: Balances past and future equally -> Standard A*
• W > 1: Trusts the heuristic more heavily -> Weighted A*
• W -> infinity: Cares only about h(n) -> Greedy Best-First Search

If you switch the visualizer above from Standard A (W = 1)* to Weighted A (W = 2)**, you can see this in action: Weighted A skips expanding node A completely and heads straight down S -> B -> E -> G in 4 steps instead of 5. You lose the mathematical guarantee of finding the absolute cheapest path in every possible graph, but in practice you often get a near-optimal path much faster.

Part 2: Local Search (When the Path Doesn’t Matter)

Everything we studied in Days 1 and 2 (BFS, DFS, UCS, Greedy, A*) assumed that the path to the goal is what we want: a turn-by-turn driving route or a sequence of moves in a puzzle.

Local search starts from a completely different premise: sometimes we only care about the final state, not the sequence of steps we took to get there. Think about arranging components on a circuit board, scheduling flights, or placing N queens on a chessboard so none attack each other. Nobody cares which queen you slid first; they only care about the final board configuration.

Because local search throws away the path history and the frontier, its memory footprint is tiny:

Tree / Graph Search:  Stores paths + entire Frontier in memory
Local Search:         Stores only the current candidate state(s)

1. Hill Climbing (Greedy Local Search)

Hill climbing is the simplest local search algorithm. Picture standing on a hilly terrain in thick fog with an altimeter:

1. Look at the immediate neighbors of your current state.
2. Move to the neighbor with the highest value (or lowest cost).
3. Repeat until no neighbor is better than where you are standing.

It requires no frontier and almost zero memory: just the current state.

2. The Catch: Getting Stuck at a Local Maximum

Because hill climbing never looks more than one step ahead and never allows a downhill move, it is easily trapped by the shape of the landscape:

Value
  ^
  |                           GLOBAL MAX (G = 100)
  |                              /\
  |        LOCAL MAX (A = 68)   /  \
  |              /\            /    \
  |             /  \__________/      \
  |    START (S)
  +------------------------------------------> States

• Local Maximum: A peak that is higher than all of its immediate neighbors, but lower than the true Global Maximum elsewhere in the state space.
• If you select Hill Climbing in the visualizer above, watch how it climbs from S (val=40) to A (val=68) because 68 beats B (62). Once at A, its only options are C (55) and D (64). Since both are lower than 68, Hill Climbing halts at A and never discovers G (100).

3. Variations That Help Hill Climbing Escape

We covered three practical ways to improve basic hill climbing:

1. Stochastic Hill Climbing: Instead of always picking the single steepest uphill neighbor deterministically, choose randomly among the uphill neighbors (with higher probability for steeper improvements). That randomness helps avoid getting funneled into the exact same trap every run.
2. First-Choice Hill Climbing: When a state has thousands of possible neighbors, evaluating all of them just to take one step is too slow. First-Choice generates neighbors randomly one at a time and immediately jumps to the first neighbor that is better than the current state.
3. Random-Restart Hill Climbing: “If at first you don’t succeed, try, try again.” Run hill climbing until it gets stuck. If the result isn’t good enough, pick a brand-new random starting state and climb again, keeping the best state found across all runs. (Try Random-Restart in the visualizer above to see Attempt 2 start at B and climb straight to G!)

Part 3: Beam Search (k States Working Together)

Hill climbing is fragile because it stakes everything on one current state (k = 1). If that single state walks into a dead-end ridge, the search is over.

Beam Search keeps the best k candidate states alive at every step:

1. Start with k states on the beam.
2. Generate all successors of all k states.
3. Rank the pool and keep only the top k states for the next round.
4. Repeat until a goal is reached or the beam stops improving.

(Note: Unlike running k separate random restarts that never talk to each other, Beam Search pools all successors together. If state A produces terrible children and state B produces two great children, the next beam will happily adopt both of B’s children and drop A’s branch entirely!)

One Important Beam Search Subtlety

What if one of the states currently on your beam (say, score = 90) generates children that are all worse (say, scores 70 and 75)? If you blindly replace the current beam with only newly generated children, you would throw away your best state!

A safer implementation pools the current beam states AND their better successors together and keeps the best k overall, stopping once the beam can no longer improve.

Comparing Everything We Covered in Day 3