Artificial intelligence
Cambridge AS & A Level Computer Science 9618 · Paper 3 · Unit 18
Paper 3 · Unit 18. Graphs, Dijkstra, A*, machine learning and neural networks.
1. Graphs in AI
A graph is a set of nodes (vertices) joined by edges, which may have weights (e.g. distance or cost). AI uses graphs to represent maps, networks and states of a problem, and searches them to find the best route or decision.
2. Dijkstra’s algorithm and A*
Dijkstra’s algorithm finds the shortest path from a start node to every other node: set all distances to infinity (start = 0); repeatedly visit the unvisited node with the smallest distance, and update its neighbours if a shorter route is found through it.
Try it: Dijkstra’s algorithm step by step
Edges: A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6, E–F 3. Start node: A.
A* adds a heuristic h(n), an estimate of the remaining distance to the goal (e.g. straight-line distance). It chooses the node with the smallest f(n) = g(n) + h(n), where g(n) is the cost so far. This usually finds the goal faster by exploring fewer nodes.
3. Machine learning
Machine learning lets a system improve its performance from data without being explicitly programmed for every case.
| Type | Description | Example |
|---|---|---|
| Supervised | Trained on labelled data (inputs with known outputs) | Spam filtering, predicting house prices |
| Unsupervised | Finds patterns in unlabelled data | Grouping customers into segments |
| Reinforcement | An agent learns by trial and error, receiving rewards or penalties | Game-playing, robots |
Deep learning uses artificial neural networks with many hidden layers. Each connection has a weight; during training, back propagation compares the output with the expected output and adjusts the weights backwards through the network to reduce the error. Regression predicts a continuous value from the relationship between variables.
4. Examiner tips
- Dijkstra: show the table after each node is visited.
- A* heuristic estimates the remaining cost; it does not have to be exact.
- Name the learning type from the scenario: labelled data means supervised.
- Back propagation adjusts weights to reduce error.
5. Practice questions
Practice: answer and check instantly
Type a short answer, then press Check or Enter.
Show answer
13: A → C → B → D → E → F = 2 + 1 + 5 + 2 + 3.
Show answer
A*.
Show answer
Supervised learning.
Show answer
Reinforcement learning.
Show answer
Unsupervised learning.
Show answer
Back propagation.
Show answer
h(n), the heuristic.
Show answer
Edges.
Exam-style questions
9. Explain how A* differs from Dijkstra’s algorithm. [3]
Show mark guide
A* uses a heuristic estimate of the distance to the goal [1] · it chooses the node with the lowest f = g + h, where g is the cost so far [1] · so it focuses the search towards the goal and usually visits fewer nodes [1].
10. Describe how back propagation trains an artificial neural network. [3]
Show mark guide
Inputs are fed forward to produce an output [1] · the output is compared with the expected output to find the error [1] · the error is sent backwards and the weights are adjusted to reduce it, repeated many times [1].
6. Topic test: predict your grade
Topic test: predict your grade
15 questions, about 10 minutes. Answer them all, then press Mark my test.
Frequently asked questions
How does Dijkstra’s algorithm work?
Set all distances to infinity except the start node, then repeatedly visit the unvisited node with the smallest distance and update its neighbours if a shorter route is found.
What is the difference between A* and Dijkstra’s algorithm?
A* adds a heuristic estimate of the remaining distance to the goal and chooses the node with the lowest total of cost so far plus heuristic, so it usually explores fewer nodes.
What are the types of machine learning?
Supervised learning uses labelled data, unsupervised learning finds patterns in unlabelled data, and reinforcement learning learns through rewards and penalties.