Walking man's delight

[bonanova]

Enough with traveling salesman who hate long road trips.

Mario Andretti has joined the team, and he loves to drive!

His route today comprises eight towns, placed at the corners of an octagon.

Here are their coordinates:

Edit: 7 and 8 are labeled incorrectly. They should be switched.

+---+-+-+

City x y

+---+-+-+

1 0 2

2 0 4

3 2 6

4 4 6

5 6 4

6 6 2

7 4 0

8 2 0

+---+-+-+

The inter-city distances, to save some calculations, are N-S and E-W distances of 6, along with four different diagonal distances of 2.828, 4.472, 5.657 and 6.083 6.325

If Mario begins driving at city 1 (coordinates 0 2) and drives until he has visited them all, how far will he be able to drive, and what city will he visit last?

If his objective is to return to his hotel in City 1 after visiting the other cities, how long of a trip could he accomplish?

Edited May 15, 2013 by bonanova
Switch 7 and 8 on the graph and correct 6.063 to 6.325

[BMAD]

Enough with traveling salesman who hate long road trips.

Mario Andretti has joined the team, and he loves to drive!

His route today comprises eight towns, placed at the corners of an octagon.

Here are their coordinates:

salesman.gif

+---+-+-+

City x y

+---+-+-+

1 0 2

2 0 4

3 2 6

4 4 6

5 6 4

6 6 2

7 4 0

8 2 0

+---+-+-+

The inter-city distances, to save some calculations, are N-S and E-W distances of 6, along with four different diagonal distances of 2.828, 4.472, 5.657 and 6.083

If Mario begins driving at city 1 (coordinates 0 2) and drives until he has visited them all, how far will he be able to drive, and what city will he visit last?

If his objective is to return to his hotel in City 1 after visiting the other cities, how long of a trip could he accomplish?

Are you saying what is the greatest path?

[bonanova]

Yes. But visit each city only once.

[BMAD]

Yes. But visit each city only once.

If we are able to backtrack or drive aimlessly then it could take infinitely long.

I am working out the possible distance if a person must go in straight lines. Now my question is, can they cross over the same point? If i go diagonal between two cities, when going to a different city may i travel back over a common point or must each visit be completely unique. In other words in my travels between three cities may my path form a modified x (intersecting segments) or would i have to more likely make a U (no intersection segments)?

[BobbyGo]

My first instinct is to have the salesman criss-cross as much as possible. The route I would take (just a guess, haven't verified) is 1, 5, 2, 6, 3, 8, 4, 7 for a total of 41.989 units traveled.

[bonanova]

Yes. But visit each city only once.

If we are able to backtrack or drive aimlessly then it could take infinitely long.

I am working out the possible distance if a person must go in straight lines. Now my question is, can they cross over the same point? If i go diagonal between two cities, when going to a different city may i travel back over a common point or must each visit be completely unique. In other words in my travels between three cities may my path form a modified x (intersecting segments) or would i have to more likely make a U (no intersection segments)?

Assume a network of straight roads connects every pair of cities.

I did not draw all the roads to keep the map uncluttered, but gave the distances.

That may have been a source of confusion.

Visit every city once and only once, using those roads.

No trips to Disney World.

Paths can cross.

[bonanova]

My first instinct is to have the salesman criss-cross as much as possible. The route I would take (just a guess, haven't verified) is 1, 5, 2, 6, 3, 8, 4, 7 for a total of 41.989 units traveled.

Good guess BG, but I found one a little longer.

This is the correct open route.

P.s. I think it's more challenging than finding the shortest route, which in this case is trivial.

If people like this genre I will post another.

Edited May 15, 2013 by bonanova
This solution is optimal.

[kingofpain]

152674831?

[BobbyGo]

Hmm... just noticed that the coordinates listed for points 7 (4,0) and 8 (2,0) are switched on the graph. It labels 7 at (2,0) and 8 at (4,0). Which set is correct?

[Xavier]

on the graphic, 7 and 8 are inverted, also it seems the 6.083 distance whould have been 6.325

not returning: 1 5 2 6 3 8 4 7 for 42.63

returning: 1 5 2 7 3 8 4 6 1 for 47.10

[bonanova]

on the graphic, 7 and 8 are inverted, also it seems the 6.083 distance whould have been 6.325

not returning: 1 5 2 6 3 8 4 7 for 42.63

returning: 1 5 2 7 3 8 4 6 1 for 47.10

Xavier is correct on both counts. I've modified the OP. Square root of 40 is 6.325.

Edit: both of these paths are just shy of optimal.

[bonanova]

152674831?

The longest closed path does not have any (chess) Knight moves.

All the inter-city distances except for two are longer than 6.

But the two that aren't are the 5.6 links.

[bonanova]

My first instinct is to have the salesman criss-cross as much as possible. The route I would take (just a guess, haven't verified) is 1, 5, 2, 6, 3, 8, 4, 7 for a total of 41.989 units traveled.

BG has the longest (non-returning) path.

I have marked the puzzle solved, but we still have the longest (closed-loop) path to determine.

(Post solutions in terms of the corrected 7-8 numbering and corrected 6.325 distance.)

[BobbyGo]

Non-Returning: 1, 5, 2, 6, 3, 7, 4 ,8 for 42.957

Returning: 1, 4, 7, 5, 2, 8, 3, 6, 1 for 47.278

[bonanova]

Non-Returning: 1, 5, 2, 6, 3, 7, 4 ,8 for 42.957

Returning: 1, 4, 7, 5, 2, 8, 3, 6, 1 for 47.278

You have the longest non-returning path.

The returning path can be slightly longer.

I'm not sure which order of 7 and 8 you are using, but I see one path that is too short to use.

There are no (chess) Knight moves, like 7-5 and 2-8 (using the correct 7 8 labeling).

If you are using the original 8 7 labeling you are not using knight moves, but too many 1-4 type moves.

Clue for those still working on this the longest total length is 47.97, and from that you can get the distribution of city-city distances used, and work out the path.

Try my next, harder puzzle just posted.

[BobbyGo]

Non-Returning: 1, 5, 2, 6, 3, 7, 4 ,8 for 42.957

Returning: 1, 4, 7, 5, 2, 8, 3, 6, 1 for 47.278

You have the longest non-returning path.

The returning path can be slightly longer.

I'm not sure which order of 7 and 8 you are using, but I see one path that is too short to use.

There are no (chess) Knight moves, like 7-5 and 2-8 (using the correct 7 8 labeling).

If you are using the original 8 7 labeling you are not using knight moves, but too many 1-4 type moves.

Clue for those still working on this the longest total length is 47.97, and from that you can get the distribution of city-city distances used, and work out the path.

Try my next, harder puzzle just posted.

Doh... mixed up 7 and 8 on the returning...