🤖 A Level · Chapter 18
Artificial Intelligence
Graphs · Graph Search Algorithms · Neural Networks · Machine Learning · Deep Learning
Graphs in AI
What is a graph?
A graph is a data structure consisting of nodes (vertices) connected by edges. In AI, graphs model real-world networks: maps, social connections, state spaces, decision trees.
| Term | Meaning | Example |
|---|---|---|
| Node / Vertex | A point in the graph | City on a map |
| Edge | Connection between two nodes | Road between cities |
| Weight | Cost/distance on an edge | Distance in km |
| Directed graph | Edges have direction (one-way) | Twitter follows |
| Undirected graph | Edges go both ways | Facebook friendships |
| Path | Sequence of connected nodes | Route from A to B |
Dijkstra’s Algorithm — Shortest Path
Purpose
Finds the shortest path from a source node to all other nodes in a weighted graph (no negative weights). Guarantees optimal solution.
Graph: A→B(4), A→C(2), B→D(3), C→B(1), C→D(5)
Initialise: dist[A]=0, all others=∞
Unvisited: {A, B, C, D}
Step 1 — Visit A (dist=0):
Update B: min(∞, 0+4)=4
Update C: min(∞, 0+2)=2
Mark A visited. Unvisited: {B, C, D}
Step 2 — Visit C (dist=2, smallest unvisited):
Update B: min(4, 2+1)=3 ← improved!
Update D: min(∞, 2+5)=7
Mark C visited. Unvisited: {B, D}
Step 3 — Visit B (dist=3):
Update D: min(7, 3+3)=6 ← improved!
Mark B visited. Unvisited: {D}
Step 4 — Visit D (dist=6):
No unvisited neighbours.
Final shortest paths from A:
A→A: 0
A→B: 3 (via C)
A→C: 2
A→D: 6 (via C→B)
Key rule
Always visit the unvisited node with the smallest current distance. Greedy approach — locally optimal choices lead to globally optimal path.
A* Algorithm — Heuristic-Guided Search
A* vs Dijkstra
Dijkstra explores all nodes equally. A* adds a heuristic — an estimate of remaining distance to goal — to prioritise promising paths. This makes A* faster for finding the path to a specific target.
f(n) = g(n) + h(n)
Where:
g(n) = actual cost from start to node n
h(n) = heuristic estimate from n to goal
(e.g. straight-line/Euclidean distance)
f(n) = total estimated cost through n
A* always expands the node with lowest f(n)
✅ A* advantages
- Faster than Dijkstra for point-to-point search
- Optimal if heuristic is admissible (never overestimates)
- Widely used in games, GPS, robotics
⚠️ A* limitations
- Requires a good heuristic function
- Memory-intensive — stores open/closed lists
- Heuristic quality affects performance
Exam note
You will NOT be required to write code for graphs. You must understand the algorithms and be able to trace them on a given graph diagram.
Artificial Neural Networks
Inspiration
Modelled on biological neurons in the brain. Each node receives inputs, applies a weight and activation function, and passes output to the next layer.
x₁
x₂
x₃
Input
Layer
Layer
→
h₁
h₂
h₃
h₄
Hidden
Layer
Layer
→
h₁
h₂
h₃
Hidden
Layer 2
Layer 2
→
y₁
y₂
Output
Layer
Layer
| Component | Role |
|---|---|
| Input layer | Receives raw data (pixel values, sensor readings, etc.) |
| Hidden layer(s) | Learns intermediate features and patterns |
| Output layer | Produces final result (class label, prediction, etc.) |
| Weight | Strength of connection — adjusted during training |
| Bias | Offset that shifts the activation function |
| Activation function | Introduces non-linearity (e.g. ReLU, sigmoid) |
Back Propagation
How learning happens
- Forward pass: Input flows through the network → prediction is made
- Error calculated: Compare prediction to correct answer (loss function)
- Backward pass: Error is propagated backwards through the network
- Weights updated: Each weight adjusted using gradient descent to reduce error
- Repeat thousands of times → network gradually improves
Regression methods predict a continuous numerical value (unlike classification which predicts a category).
- Linear regression: Fits a straight line to data (y = mx + c). Minimises sum of squared errors.
- Logistic regression: Predicts probability (0–1) — used for binary classification
- Polynomial regression: Fits a curve to non-linear data
In neural networks, regression is the process of finding the best weights — minimising a cost function through gradient descent.
Machine Learning Categories
✅ Supervised Learning
Trained on labelled data — input/output pairs. Model learns to map inputs to known outputs.
Examples: Image classification, spam detection, price prediction
🔍 Unsupervised Learning
Trained on unlabelled data. Model finds hidden patterns and structure on its own.
Examples: Customer segmentation, anomaly detection, recommendation systems
🎮 Reinforcement Learning
Agent learns by interacting with an environment. Receives rewards for good actions, penalties for bad ones.
Examples: Game-playing AI (chess, Go), robot navigation, trading bots
Deep Learning vs Machine Learning
| Machine Learning | Deep Learning | |
|---|---|---|
| Architecture | Traditional algorithms (decision trees, SVMs) | Multi-layer neural networks (many hidden layers) |
| Feature engineering | Human must manually select features | Automatically learns features from raw data |
| Data requirements | Works with smaller datasets | Needs very large datasets |
| Compute needs | Modest CPU | High — requires GPUs/TPUs |
| Interpretability | Usually explainable | Often a “black box” |
| Best for | Structured/tabular data | Images, speech, text, video |
Analogy
Machine learning is like teaching someone rules then giving examples. Deep learning is like showing a child thousands of pictures of cats until they just know what a cat looks like — without anyone explaining what ears or whiskers are.
⚡ Exam Essentials
- Know graph terminology: node, edge, weight, directed/undirected
- Trace Dijkstra’s algorithm on a weighted graph — show distance table updating
- Explain A* = g(n) + h(n) and why the heuristic makes it faster
- Describe structure of ANN: input, hidden, output layers + weights
- Explain back propagation in plain English (forward pass, error, backwards update)
- Distinguish supervised, unsupervised, and reinforcement learning with examples
- Compare Deep Learning vs Machine Learning — when to use each