- Home
- 3D printing
- Cars
- Cats
- CNC machines
- Computers
- Electronics
- Lightwave
- Miscellaneous
- Music
- Software
- Steel

- Active project
- Electronics
- SVN
- Source code
- Windows

# Travelling salesman problem

*This is quite long, I'm afraid!*

One of the most well-known problems in computing (or mathematics) is known as the travelling salesman problem. This is basically all about a salesman who has to travel to a certain number of cities and they need to know the quickest way to achieve this.

Working out the most efficient way to drill the holes on the board is basically this problem.

And the problem is quite difficult to solve - if you had 5 different locations, then there are 5x4x3x2(x1) possible answers (also known as 5 factorial, or 5! for short). If it took 1 second to calculate a solution, then it'll take you 120 seconds to find all the answers. If you add a new location, then it's now 6! - or 720 seconds. A seventh point increases this to 5040 seconds, or 1 hour 24 minutes.

The board above has 130 points on it, which means that there are 6.466x10^{219} possible solutions. Even if it took 1µs (1 millionth of a second) to find the answer, it'll take 6.466x10^{213} seconds - or 7.484x10^{208} days. Or 2.0499x10^{206} years. In case you don't know what that is, here it is in full:

20,492,228,462,305,400,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000,000,

000,000,000,000,000,000,000,000,000 *years*...

I *think* that's right!

Since I can't wait that long - and nor can most people - you don't normally try every possible combination to see what is the best.

As it is a well-known problem, there are plenty of people who have written up on this. But copying someone else is not any kind of challenge to me!