Maths and computer science · Solid · Dissertation or artefact

Quick routes for the travelling salesman: a maths EPQ idea

Why it works as an EPQ

The exact problem is hard, but you can bound the best answer and measure how good fast methods are.

Scope and difficulty

Solid. Solid. Small real networks, two heuristics and a lower bound.

The maths

Builds on these A Level topics: Algebra and functions · Numerical methods.

You would learn:

• Graphs and minimum spanning trees
• Nearest neighbour and improvement heuristics
• Lower bounds

Learning maths beyond the course is expected in a maths EPQ, but you must understand and explain everything you use.

One possible plan

1. Explain why checking every route is impossible for large n.
2. Apply nearest neighbour and 2-opt to real towns.
3. Find lower bounds with spanning trees.
4. Judge how close the heuristics get, and when that is good enough.

Pitfalls

• Comparing methods on one example only.
• Confusing upper and lower bounds.

Where to start reading

• A Decision Maths textbook chapter on the travelling salesman problem
• Search for: 2-opt heuristic travelling salesman

Prefer books, lecture notes, journal articles and official data to a single website, and record every source as you read (how to reference).

Making something? Read the artefact guide first: an artefact still needs a research-based written report.

Similar ideas

• How computers fake randomnessHow can a computer, which follows rules, produce random numbers, and how random are they?Computer scienceSolidDissertation or artefact
• Hash collisions and the birthday problemHow likely are two different files to share a hash, and what does the birthday problem say about security?Computer scienceSolidDissertation
• How RSA keeps payments secureHow does RSA encryption keep online payments secure, and what would it take to break it?Computer scienceSolidDissertation or artefact
• Which sorting algorithm is fastest?Which sorting algorithm is fastest in practice, and does Big O notation tell the whole story?Computer scienceSolidDissertation or artefact

All maths and computer science ideas · all 93 ideas

Your EPQ must be your own work. These pages coach: ideas, structure, checklists and planning. Submitting text, proofs, code or analysis written by someone else or by an AI tool as your own is malpractice. How to use help and AI honestly.