Thread: Travelling Salesman

I have an urgent question about the travelling salesman problem.

I have to find four optimal solutions to the travelling salesman problem for 5 cities with given co-ordinates, using 12 randomly generated numbers found with the Linear Congruental Method. I have generated the 12 numbers but then don't know what to do next.

The question says something about using the Monte Carlo method but I don't know how to do that. Any help would be much appreciated! Thanks!

Originally Posted by cdevine

I have an urgent question about the travelling salesman problem.

I have to find four optimal solutions to the travelling salesman problem for 5 cities with given co-ordinates, using 12 randomly generated numbers found with the Linear Congruental Method. I have generated the 12 numbers but then don't know what to do next.

The question says something about using the Monte Carlo method but I don't know how to do that. Any help would be much appreciated! Thanks!

A tour consists of a random permutation of the cities. Find out how to generate random permutations (google for it or look in Knuth's TAOCP Semi-Numerical Algorithms).

Now in a loop generate a random tour, compute the distance keep it if it is the best found so far.

When you finish you will have a tour that is better than most.

CB

Is that the same method you should use if you're not doing it through computer programming?

Thanks