Maths IA · Geometry and trigonometry · topic 29 of 40

Shortest route: how good is a quick heuristic? · IB Maths IA idea: guide, sample graph and step-by-step plan

small enough to check = good

Deliver to six places and visit each once: how many routes are there, and does the obvious one win? You're going to find out how far off the quick method can be.

Difficulty●●○ Medium
KitMap, spreadsheet or Python, GDC
TimeAbout 12 to 15 hours
FitsAI HL
  • ✓ you like maps, routes and puzzles
  • ✓ you enjoy comparing a quick method with the exact answer
  • ✓ you can use a spreadsheet or code to check every tour

The big idea

← the comparison is your result

The travelling salesman problem asks for the shortest route that visits every point once and returns. Graph theory is AI HL content: on SL or AA you would be teaching yourself a whole topic, so pick another. The number of routes grows very fast, so for a small case you can check them all, and for bigger ones you need a heuristic. Reduce the problem to a small case, find the best route by checking everything, and compare it with a quick method such as nearest neighbour. The comparison is the exploration: how far off, and when? A lower bound shows the best route cannot be shorter than a stated value. Strong work says what 'distance' means and why, and counts and checks every route in the small case.

Make it yours: pick one twist

Copying a classic won't show your choices. Pick one of these (or invent your own) and your IA becomes yours.

Swipe for more twists →

Count the routes

Work out how many different tours there are for n points, and show the growth.

→ A counting argument to explain why brute force stops working, and a link to the graph of growth.
Add a lower bound

Use a method such as the deleted-vertex or minimum spanning tree bound to say how short the best route could be.

→ A range for the best route, so you can say how close the heuristic is, even when you cannot check every tour.
Compare heuristics

Nearest neighbour against another quick method, from several starting points.

→ A comparison with a number (tour length against best) and a discussion of when each does badly.
Choose the distances yourself

Straight-line distance, road distance or travel time between places.

→ The 'weights' on the graph are your decision. The best route may change with them, so justify the choice.
Use a real set of places

Your own list of places: shops, friends' houses or sights in a city.

→ Personal data and a reason for every choice, but you must keep the case small enough to check by hand.
Test with random points

Generate many random sets of points and measure how far off the heuristic is.

→ A statistical comparison, with a mean gap and a measure of spread, and a check of how many cases is enough.

Your Maths IA research question: run the check

say how many points, and why

Write your own question first. Then make sure it ticks every box:

  • Names the number of points and how they are chosen (real places? random points?).
  • Says what 'distance' means between two points and why you chose it.
  • Names the heuristic and the way you will find or bound the best route.
  • Says how you will measure the gap between them: a percentage over the best tour.
  • Is narrow enough: a small case you can check fully, then one extension.
  • Can be answered with numbers you can reproduce.

Get your RQ checked · S$29

The picture to draw

Six points, a quick route and the best route. Draw yours on your own set of places, with the distances you chose.

ABCDEFstart citynearest-neighbourroute (dashed)best of all 60 tours (solid)edge weight = distance:which kind, and why?6 cities: you choosethem, with a reason

How your Maths IA could be laid out

The usual order for a topic like this, what each part needs to show, and roughly how much of your 12 to 20 pages it takes. The words are all yours.

Title page, question and rationale~1 page
Your question; the places or journey that made you ask it.
Aim and plan~0.5 page
What you will compare and how you will measure the gap.
The problem~2 pages
Points, distances, a tour and its length; a clear diagram and defined symbols. Why a complete graph with weights is a good model.
Counting the tours~1.5 pages
How many tours there are for n points, with a short argument, and what that means for checking them all.
The best tour~2 pages
A table of every tour in your small case, and the shortest. Explain how you avoided missing any.
The heuristic~2 pages
The steps of the quick method on your case, from more than one start, with the tour lengths.
Bounds and comparison~2 pages
A lower bound for the best tour, and the gap between the heuristic and the best, as a number.
Extension~2 pages
A bigger case, random points or another heuristic. At HL this is where the HL-level maths must show.
Reflection throughout~1.5 pages
What your choice of 'distance' did; where the heuristic fails and why; what a delivery company would do.
Conclusion~0.5 page
Answer with numbers, and say whether the aim was met.
Bibliography and appendixnot counted
Sources, long tables and code.

What your Maths IA graph could look like

log scale: say so on the axis

Made-up data, to show you the form of a strong graph, not the answer. Yours will look different. example only

456789101112012345678Number of points, nlog₁₀ (number of tours)all tours: log₁₀ ((n − 1)! / 2), Stirling forma heuristic's work: log₁₀ (n²)exact count (n − 1)! / 2how many tours can yourspreadsheet check in a minute?ILLUSTRATIVE · MADE-UP DATA
  • The vertical axis is logarithmic in effect: log₁₀ of a count. Say so on the axis.
  • The curve is a formula, the points exact counts. They match closely, and the small gap is worth explaining.
  • A second curve shows the work a heuristic needs, so the contrast is the message.
  • The scale lets the reader see the growth from 6 tours to ten million in one picture.
  • Another graph to consider: the heuristic's tour length divided by the best, against the number of points, from your random trials.

Your game plan

list EVERY tour in the trial run

Tick steps off as you go. We'll remember on this device.

0 of 11 done

  1. Read and predictLearn what a tour and a heuristic are. Before you calculate, predict how far off a quick method can be, in percent.
  2. Count the toursWork out how many different tours there are for small n by hand. Check against a list for n = 4.
  3. Trial run (one evening)Choose five or six places and a distance. Write the distance table. Can you list the tours without missing one?
  4. Choose your places and distancesDecide the points and what 'distance' means, with a reason. Check the table is symmetric and the triangle rule is reasonable.
  5. Find the best tourCheck every tour in the small case with a systematic list or a program. Show enough steps for a reader to repeat it.
  6. Run the heuristicApply it by hand from more than one starting point. Record each tour and its length.
  7. Bound the bestFind a lower bound on the best tour. Say how it works and why it is valid.
  8. CompareWork out the gap between the heuristic and the best, as a percentage. Look for when it fails.
  9. ExtendChoose one: more points, random cases, or a second heuristic. Say why.
  10. Reflect as you goWhat did your choice of distance change? What would a real delivery firm do differently?
  11. Write, then cut12 to 20 pages. Show one full tour calculation, then use tables. Check notation and labels, and keep long tables for an appendix.

Maths you'll need

Traps to avoid in this Maths IA

  • Choosing too many points, so the best tour cannot be checked and the 'best' is just another heuristic.
  • Missing tours in the list, so the claimed best is not the best.
  • Distances that are not defined, or a table that does not match your map.
  • Copying the standard algorithm with no comparison or insight of your own (personal engagement).
  • At HL, an exploration that is only tables of distances: bring in a bound, a counting argument or a statistical comparison.
  • Quoting the gap with no starting point: nearest neighbour depends on where you start.
  • Showing a program or a solver's output instead of explaining the steps.

More Maths IA ideas like this

Make sure it's yours

This guide shows how a topic like this is usually approached. It is not an IA. Your question, choices, data, analysis and words must be your own: change something, tell your teacher where the idea came from, and follow your school's rules on outside help.

Get your RQ checked · S$29