Thread: 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?

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

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?

Originally Posted by veronicak5678

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) ?