Artificial Intelligence (AI)

Computer Science A2 · Artificial Intelligence (AI). The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Computer Science A2 topics

The idea

A graph is a set of vertices (nodes) joined by edges. Edges can have a direction and a weight, such as a distance or a cost. AI uses graphs to model routes, game positions and links between ideas, then searches them for the best path. Dijkstra's algorithm and the A* algorithm both find the shortest path.

In machine learning a program improves from data instead of following fixed rules written by a programmer. An artificial neural network has an input layer, one or more hidden layers and an output layer. Each connection has a weight, and training adjusts the weights.

Deep learning uses networks with many hidden layers and very large data sets.

Rules to remember

Dijkstra: always visit the unvisited vertex with the smallest total distance from the start, then update its neighbours if a shorter route is found.
A*: f(n) = g(n) + h(n), where g is the cost from the start so far and h is the heuristic estimate of the cost to the goal. Expand the vertex with the smallest f.
A heuristic is admissible if it never overestimates the true cost to the goal; A* then finds the shortest path.
Supervised learning: trained with labelled data (inputs with known correct outputs). Unsupervised learning: no labels, the system finds patterns or groups itself.
Reinforcement learning: an agent learns by trial and error, with rewards for good actions and penalties for bad ones.
Back propagation: compare the output with the expected output, pass the error back through the layers and adjust the weights to reduce it; repeat many times.
Regression: finds the relationship between variables (for example a best-fit line y = mx + c) and uses it to predict a value.

Common mistake

In Dijkstra's algorithm students stop at the first route that reaches the target. A route with more edges can have a smaller total, so keep updating distances until the target is the vertex with the smallest distance still unvisited.

Worked example

A weighted undirected graph has edges A–B 3, A–C 1, B–C 1, B–D 4, C–D 6. Use Dijkstra's algorithm to find the shortest distance from A to D.

Start: A = 0. From A: B = 3, C = 1. Smallest unvisited is C (1).
Visit C: B = 1 + 1 = 2, which is less than 3, so B becomes 2. D = 1 + 6 = 7.
Smallest unvisited is B (2). Visit B: D = 2 + 4 = 6, which is less than 7, so D becomes 6.
D is now the only unvisited vertex, so its distance is final.

Answer: 6, along the path A, C, B, D.

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← Encryption, Encryption Protocols and Digital Certificates Algorithms →Take a Computer Science A2 test