+0

# The Travelling Salesman

+1
141
5

So, I'm pretty sure that the Travelling salesman problem goes something like with x points at (locations), what's the shortest route?

Wouldn't it be possible to draw all the lines connecting the dots, find the shortest one, connect it, delete extra lines connecting two nodes already in the connection, checking the two end node's lines, finding that shortest one, etc. Sorry if I said something really stupid, I'm only 11 and probably don't fully understand the problem

Guest Oct 24, 2017
Sort:

#2
+541
+1

I think I get what you're talking about:

Do you actually want to try all of the possible routes? I mean, sure, it makes sense with 4. But even there, you are doing 24 calculations. And this number goes up into the stratosphere pretty darn fast. This is one instance of a mathematical function called a factorial. To take the factorial of a number, you use the exclamation mark, and the function works like so: $$x! = x \times (x - 1) \times (x - 2) \times (x - 3) \times \dots \times 3 \times 2 \times 1$$. At numbers like 30 or so, this is impractical for human calculation; there are 6,227,020,800 different routes you could take!

helperid1839321  Oct 24, 2017
#3
+91774
+3

Here is the problem explained

I think the trick is to make the route the thinest polygon possible,  (So no cross overs of the route)

So for the 6 cities below I think the shortest route would be to work your way around the yellow hexagon.  This is of course if you are flying directly between the cities.

Melody  Oct 24, 2017
#4
+541
+1

What you said wasn't stupid at all - as a matter of fact, it sounds like you thought a lot about it.

helperid1839321  Oct 24, 2017

### 9 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details