Results 1 to 3 of 3

Math Help - Travelling Salesman

  1. #1
    Newbie
    Joined
    Apr 2009
    From
    South England
    Posts
    3

    Exclamation 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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by cdevine View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    From
    South England
    Posts
    3
    Is that the same method you should use if you're not doing it through computer programming?

    Thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Asymmetric Travelling Salesman Problem - Particular case
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 17th 2011, 03:13 AM
  2. Salesman Tour
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 6th 2011, 02:11 AM
  3. Travelling along...
    Posted in the Geometry Forum
    Replies: 2
    Last Post: July 29th 2010, 06:38 AM
  4. travelling boat problem
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: October 15th 2007, 09:55 PM
  5. Hamiltonian/Euler Problems (Travelling Salesman Prob)
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 19th 2006, 10:18 PM

Search Tags


/mathhelpforum @mathhelpforum