+0  
 
+1
955
5
avatar

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

 Oct 24, 2017
 #2
avatar+633 
+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!

 Oct 24, 2017
 #3
avatar+118578 
+3

Here is the problem explained

 

https://www.youtube.com/watch?v=SC5CX8drAtU

 

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.  laugh

 

 Oct 24, 2017
 #4
avatar+633 
+1

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

 Oct 24, 2017

0 Online Users