Computational methods

Problem recognition, divide and conquer, backtracking, heuristics, performance modelling, data mining and visualisation.

A2.9Recursion and computational thinkingA level25 min

Do this lesson in the simulator

Not every problem can be solved by a computer, and those that can are not all solved the same way. This lesson is a toolkit: what makes a problem computable in practice, how to recognise the kind of problem in front of you, and the standard methods for attacking it. You have already used several of them in this module without naming them.

Is it a problem a computer can solve?

A problem is suited to computational methods when:

it can be stated precisely, with clear inputs and a clear test of whether an answer is right;
it can be solved by an algorithm: a finite sequence of steps;
the data it needs can be represented and obtained;
the algorithm finishes in a reasonable time and memory for the sizes that matter.

"Is this route across the mat the shortest?" passes all four. "Is this the most beautiful route?" fails the first. "Try every order of visiting 20 places" passes the first three and fails the last, as you will see below.

Problem recognition is seeing that a new problem is really an old one in disguise: planning a robot's route is a shortest path problem; timetabling exams so no student has two at once is graph colouring. Once recognised, the problem can be reduced (lesson A2.4) and a known method applied.

Divide and conquer

Divide and conquer splits a problem into smaller problems of the same kind, solves those (usually recursively), and combines their answers. Binary search halves the list at each step and throws half away; merge sort halves the list, sorts each half and merges. Because the problem size halves each time, the number of levels is about log₂ n, which is why these methods scale so well.

def biggest(items, lo, hi):
    """The largest item between positions lo and hi, by divide and conquer."""
    if lo == hi:                              # one item: it is the biggest
        return items[lo]
    mid = (lo + hi) // 2
    left_best = biggest(items, lo, mid)       # conquer each half
    right_best = biggest(items, mid + 1, hi)
    if left_best > right_best:                # combine
        return left_best
    return right_best

readings = [31, 72, 18, 64, 90, 27, 55, 43]
print(biggest(readings, 0, len(readings) - 1))

Run this in the simulator

Backtracking

Backtracking builds a solution one step at a time. At each step it tries a choice; if the partial solution can still lead somewhere, it carries on; if it reaches a dead end, it undoes the most recent choice and tries the next one. Recursion suits it perfectly, because the call stack remembers every choice made so far, and returning from a call is the "undo".

Mazes, sudoku and placing queens on a chessboard are classic backtracking problems. Here, four queens must go on a 4 by 4 board, one per row, with no two in the same column or diagonal:

columns = []                      # columns[row] is the column of the queen in that row

def safe(col):
    row = len(columns)
    for r in range(row):
        c = columns[r]
        if c == col or abs(c - col) == row - r:
            return False
    return True

def place(n):
    if len(columns) == n:         # every row has a queen: solved
        return True
    for col in range(n):
        if safe(col):
            columns.append(col)   # try a choice
            if place(n):
                return True
            columns.pop()         # dead end: undo it and try the next column
    return False

place(4)
print(columns)
for col in columns:
    print(". " * col + "Q " + ". " * (3 - col))

Run this in the simulator

Heuristics

A heuristic is a rule of thumb that finds a good enough answer quickly, without guaranteeing the best one. Heuristics are used when an exact method would take far too long. A* search (module A5) uses a heuristic estimate of the distance left to decide which way to explore first.

The nearest neighbour heuristic for visiting several places is: from where you are, always go to the nearest place not yet visited. It is fast and often decent, but it can be led astray: a near place first can leave a long journey back at the end.

Performance modelling

Performance modelling predicts how a system or algorithm will behave (its time, memory or load) using a mathematical model or a simulation, instead of building it and measuring. It answers "will this be fast enough?" before the effort is spent.

The exact way to visit n places in the best order is to try every order. There are n! orders. Model the time, assuming a computer can check a million orders a second:

import math

for n in [5, 10, 15, 20]:
    orders = math.factorial(n)
    seconds = orders / 1_000_000
    print(f"{n} places: {orders} orders, {seconds:.4g} seconds ({seconds / 3600 / 24 / 365:.3g} years)")

Run this in the simulator

Ten places take under four seconds; twenty take about 77,000 years. The model shows that a heuristic is needed long before anyone writes the brute force program.

Data mining and visualisation

Data mining is searching large amounts of data to find patterns, relationships and trends that were not known in advance: which products are bought together, which sensor readings come before a failure. It works on data too big to inspect by eye, and its results are clues to be tested, not proof.

Visualisation presents data or a solution visually, as a chart, graph, map or diagram, so that people can see patterns a table of numbers hides. Even a text bar chart helps:

bumps_per_run = {"speed 40": 0.25, "speed 60": 1.0, "speed 80": 2.0}
for label, value in bumps_per_run.items():
    print(label.ljust(9), "#" * round(value * 8), value)

Run this in the simulator

Pipelining (lesson A2.8) is the last method on the list: a problem split into stages, each passing its output on to the next.

In the exam

Questions give a problem and ask which computational methods could be used and why, to explain one method (backtracking, heuristics, data mining, performance modelling, pipelining, visualisation, divide and conquer) in the context given, or to say what makes a problem suitable for a computational approach. Always apply the method to the scenario: say what the choices and dead ends are for backtracking, or what good enough means for a heuristic.

OCR A level 2.2.2

OCR asks for the features that make a problem solvable by computational methods, problem recognition, problem decomposition, divide and conquer and abstraction, and expects you to apply backtracking, data mining, heuristics, performance modelling, pipelining and visualisation to solve problems.

AQA A level 4.4.1.1, 4.4.1.8

AQA's problem-solving and problem reduction sections cover solving and checking logic problems and reducing a problem to one already solved. Heuristic methods for intractable problems appear in AQA's theory of computation section, and depth-first search, which navigates a maze by backtracking, in its graph traversal section.

Eduqas A level 1.3

Eduqas's algorithms and programs topic includes searching and sorting algorithms such as binary search and merge sort, which are divide and conquer methods; be ready to explain why halving the problem at each step is efficient.

Task: mining the run log

The starter holds a log of 12 runs, each a dictionary with the keys "robot", "speed" (a whole number) and "bumps" (how many times it hit something). Look for a pattern between speed and bumps.

Find the different speeds that appear in the log, from the data (do not type them into your code), and sort them from smallest to largest.
For each speed, print speed <speed>: <runs> runs, <mean> bumps per run, with the mean to 2 decimal places, for example speed 40: 4 runs, 0.25 bumps per run.
Finally print most bumps: speed <speed>, the speed with the highest mean.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

runs = [
    {"robot": "Ada", "speed": 40, "bumps": 0}, {"robot": "Bolt", "speed": 60, "bumps": 1},
    {"robot": "Cog", "speed": 80, "bumps": 2}, {"robot": "Ada", "speed": 40, "bumps": 1},
    {"robot": "Bolt", "speed": 60, "bumps": 0}, {"robot": "Cog", "speed": 80, "bumps": 3},
    {"robot": "Ada", "speed": 40, "bumps": 0}, {"robot": "Bolt", "speed": 60, "bumps": 1},
    {"robot": "Cog", "speed": 80, "bumps": 2}, {"robot": "Ada", "speed": 40, "bumps": 0},
    {"robot": "Bolt", "speed": 60, "bumps": 2}, {"robot": "Cog", "speed": 80, "bumps": 1},
]

Task: nearest first

Four stops are marked on the mat. Their positions, in cm from where the robot starts, are A (30, 30), B (0, 50), C (-30, 70) and D (-30, 60). The robot slides across and then drives up, so the distance between two points is across plus up: abs(x1 - x2) + abs(y1 - y2).

Use the nearest neighbour heuristic, starting at (0, 0): repeatedly choose the unvisited stop with the smallest distance from the current position. Plan the whole order before moving.
Print order: <names>, the stops in the order chosen separated by spaces, and length: <n> cm, the total distance of that route.
Then drive the route, visiting the stops in that order. Use position() to work out each move.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

stops = {"A": (30, 30), "B": (0, 50), "C": (-30, 70), "D": (-30, 60)}

def gap(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

Challenges

Try all 24 orders of the four stops. What is the shortest route, and how much longer is the heuristic's?
Add a fifth run speed to the log. Did your mining code need changing? If it did, it was not really finding the speeds from the data.
Change place(4) to place(8). Add a counter for how many times a choice is undone, and explain what it measures.