How long would it take for me to program a travelling salesman program with 5 nodes?

Question

I'm considering doing a travelling salesman problem for my computing coursework and would like to know how long a standard computer would take to work out the shortest route between 5 different places. I just want to know if the project is viable. Thanks in advance! I will be using VB express.

Answer 1

How many possible routes are there? Informally, surely not many? Formally, I'll let you work that out. How long would it take you with a paper and pencil to list them and find the shortest? Surely less than 5 minutes? So that gives you an idea that it's not going to tax even a slow computer.

It might be an idea to do the paper and pencil thing for 5 and 6 nodes and make sure you understand what happens as the number of nodes increases, and hence why this problem starts to get hard as the nunmber of nodes gets big.

Answer 2

A straightforward solution of Traveling Salesman Problem with 5 places requires enumerating 5! paths. 5! = 1*2*3*4*5 = 120. Enumerating 120 paths has not been a big deal for any modern computer since, I guess, 80's.

But of course, If you want to make it slow, you can always write your program awfully badly, especially in VB.