Community resourceWorksheet

OCR H446 2.3.1 A star and heuristics

Part 14 of 16 · H446 2.3.1 · Algorithms

A star is not Dijkstra with relabelled numbers, and H446 2.3.1 expects students to calculate g, h and f and to say what the heuristic is doing to the search. This worksheet works the selection rule through frontier scores, then tests three different heuristics on the same nodes so students can see informativeness and overestimation as separate issues.

Students will:

  • calculate g, h and f for frontier nodes and select the next node from them
  • recalculate a selection after a cheaper route lowers a node's known cost
  • compare A star with Dijkstra on goal information, nodes explored and stopping
  • judge whether given heuristic values would still allow an optimal result
  • explain what a zero heuristic does to the search and the risk in an overestimate

Inside: 6 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell and 3 written answers. 28 marks, about 30 to 45 minutes.

Series: H446 2.3.1 · Algorithms, part 14 of 16.

Shared by Coding PathwayVerified teacher

  • 11 cells
  • About 30 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

A star and heuristics

A* combines known route cost with an estimate of remaining cost. It is not Dijkstra with labels changed. OCR expects calculation, trace and explanation of the heuristic.

By the end, you will be able to

  • calculate g, h and f;
  • choose and update frontier nodes;
  • explain how heuristic quality changes exploration;
  • distinguish A* from Dijkstra and state assumptions.

Reactivate: Dijkstra selects smallest known g only.

Three values, one selection rule

A star cost modelg(n)known cost from starth(n)estimated cost to goalf(n)g(n) + h(n)+=Choose the frontier node with smallest f; update routes when a lower g is found.If h = 0 everywhere, the selection rule reduces to Dijkstra's.

Worked frontier: P has g=6,h=4 so f=10; Q has g=8,h=1 so f=9. A* selects Q even though P has smaller known cost. If a better route to a frontier node lowers g, recompute f.

Multiple choice1 mark

Frontier X has g=4,h=7; Y has g=8,h=1. Which is selected?

  • AX because g is smaller
  • BY because f=9 is smaller than 11
  • CX because h is larger
  • DBoth because Dijkstra ignores h

Worked heuristic reasoning

A straight-line distance can estimate road distance: it should not exceed the true remaining route if optimality is required (admissible). h=0 provides no goal direction and reduces the selection score to Dijkstra's g. An overestimate may explore less but can miss the optimal route; a weak underestimate stays correct but may explore more.

Stopping rule: do not stop merely because the goal is first generated as a neighbour. Stop when the goal is selected from the frontier as the lowest-priority f entry under the stated A* method; at that point its route is reconstructed through predecessors. Do not continue exploring every route as though performing an exhaustive Dijkstra table once the A* goal condition has been met.

Written answer6 marks

For frontier nodes A(g=5,h=6), B(g=7,h=2), C(g=3,h=9), calculate f, choose the next node, then recalculate if a new route lowers C's g to 1.

Show arithmetic and selection before/after update.

Students type their answer here.

Written answer8 marks

Compare A* with Dijkstra using selection score, goal information, explored nodes, stopping behaviour and conditions for an optimal result.

Do not say both always choose smallest edge.

Students type their answer here.

Independent transfer: evaluate heuristics

A map has actual remaining costs from nodes P,Q,R of 8,5,3. Consider h1=(0,0,0), h2=(6,4,2), h3=(9,4,2).

Written answer8 marks

Classify each heuristic as informative/admissible for these nodes, explain likely search behaviour, and identify the risk in h3.

Compare each estimate with actual remaining cost.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks5 marks
In A*, completion 1 is the known route cost and completion 2 estimates remaining cost. Their sum is completion 3. The next node is selected from the completion 4 by lowest total. A heuristic that never overestimates is completion 5.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.