levo
Get notified

Algorithms

The A* algorithm

  • 3 things to know
  • Component 02

Overview

Recall questions on the A* algorithm and its relation to Dijkstra's, heuristics and g, h and f values, admissible heuristics, a worked A* search, checking admissibility, what the heuristic gains, poor heuristics, and applications of A*.

What you need to know

Answer each one before you reveal it.

Your recallNot started
Key term

Define g, h and f as A* uses them.

Who and when

S joins A with weight 2 and B with weight 2. A joins the goal G with weight 6. B joins C with weight 1, and C joins G with weight 1. The straight-line estimates to G are 3 from S, 5 from A, 2 from B, 1 from C and 0 at G. A* run from S finds the route S, B, C, G. Which node did A* never expand, and what would Dijkstra's algorithm have done?

Key term

For the graph S–A 2, S–B 2, A–G 6, B–C 1, C–G 1 with heuristics 3, 5, 2, 1, 0, verify the heuristic is admissible.

Questions from this subtopic

Each one with the model answer underneath.

  1. 1

    What is the A* algorithm and how does it relate to Dijkstra's?

    Model answer

    A* is a shortest-path algorithm that works exactly like Dijkstra's, except that when it chooses the next node to expand it does not use the distance travelled alone. It adds an estimate of the distance still to go, so the search is steered towards the destination instead of spreading equally in all directions.

  2. 2

    What is a heuristic in this context?

    Model answer

    An estimate, calculated by a rule of thumb, of the cost of getting from a given node to the destination. It is not measured by exploring the graph; it is computed cheaply from what is known about the node, such as its position, so that it costs almost nothing to obtain.

  3. 3

    Define g, h and f as A* uses them.

    Model answer

    For a node, g is the actual cost of the best route found so far from the start to that node. h is the heuristic estimate of the cost from that node onwards to the destination. f is the sum of the two, an estimate of the total cost of a route through that node, and A* always expands the unvisited node with the smallest f.

  4. 4

    What does it mean for a heuristic to be admissible, and why does it matter?

    Model answer

    An admissible heuristic never overestimates the true remaining cost to the destination; it may be exactly right or too low, but never too high. It matters because it is the condition that guarantees A* returns a genuinely shortest path. If a heuristic overestimates, A* can dismiss the route that was actually cheapest and return a worse one.

  5. 5

    Give an example of an admissible heuristic for route finding, and explain why it is admissible.

    Model answer

    The straight-line distance from a junction to the destination. It is admissible because no road route can be shorter than the straight line between two points, so the estimate can never exceed the true road distance. On a grid where movement is restricted to horizontal and vertical steps, the number of squares across plus the number of squares up serves the same purpose.

  6. 6

    What happens to A* if the heuristic is zero for every node?

    Model answer

    It becomes Dijkstra's algorithm exactly. With h always zero, f equals g, so the node chosen next is simply the one with the smallest distance from the start, which is Dijkstra's selection rule. Dijkstra's is therefore the special case of A* with no guidance about where the destination is.

See the rest and revise

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.

1Closed book
2Open book
3Closed book

See a huge jump in your memorisation

Answer cold, learn it, then prove it stuck. Levo tracks the jump between your first attempt and your last.

Processors: Structure, Performance and Types
Input, Output and Storage
Systems Software
Applications Generation

Cram a whole paper in one sitting

Sort every topic into what you know and what you do not, then drill only the weak ones.

If it matches, the search .
succeedsfailsrestarts

Blank Blitz consolidates the facts

Rapid timed gap-fills on the terms and numbers you need to recall without thinking.

A0 + 0 gives 0.
B0 + 1 gives 1.
C1 + 1 gives 0 carry 1.

Build It trains answer structure

Assemble a full-mark answer from its marking points, in the order an examiner wants them.

A global variable means a variable reachable from anywhere in the program.
TrueFalse

Test It catches misconceptions

Spot the fault in a statement. The traps are the mistakes students actually make.

721941163128510

Brain Breaks between sessions

Short focus games to reset attention, so the next set lands better than the last.

Every question in Algorithms, on a schedule.

Attempt a question from memory, write the correct version, then attempt it again. Levo records the jump between your first attempt and your last, and brings each question back on the day you are due to forget it.

Start revising, £5 a monthSee how the method works

Or £46 a year, about £3.83 a month. Cancel anytime.