Results 1 to 4 of 4

Math Help - Salesman Tour

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    225

    Salesman Tour

    Find the shortest tour through the points of a (a) 3 3 square grid; (b) 4 4 square grid; (c) 5 5 square grid; (d) generalize to n x m grid.

    I can draw a tour on 3x3 with 9 edges, 8 of length 1 and 1 of length root2 (if the pts are 1 apart). Is this the shortest? How do I know? What about mxn?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,035
    Thanks
    49
    I think you're meant to take a 3 3 square grid to mean 4 4 vertices which are therefore (and this is the bit that matters) joined only by horizontal and vertical edges (of length 1).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    225
    Then I guess the optimal cycle on n vertices has n edges, so the 3x3 has 16 edges, the 4x4 has 25 edges... how can I be sure that an optimum cycle exists?
    Last edited by veronicak5678; March 5th 2011 at 02:50 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,035
    Thanks
    49
    Quote Originally Posted by veronicak5678 View Post
    Then I guess the optimal cycle on n vertices has n edges, so the 3x3 has 16 edges, the 4x4 has 25 edges... how can I be sure that an optimum cycle exists?
    Yes that's the next stage. You could start by sketching a few cases to come up with another guess: as to... in what kinds of cases does and doesn't the cycle exist? Then prove each. Proof that it exists is easy enough if you find a simple form of it - a spiral... (kinda) ?
    Last edited by tom@ballooncalculus; March 6th 2011 at 02:51 AM. Reason: kinda
    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. Travelling Salesman
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: April 27th 2009, 05:08 AM

Search Tags


/mathhelpforum @mathhelpforum