• 0

Walking man's delight

Question

Posted (edited) · Report post

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:

post-1048-0-45677600-1368577451_thumb.gi

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 by bonanova
Switch 7 and 8 on the graph and correct 6.063 to 6.325
0

Share this post


Link to post
Share on other sites

15 answers to this question

  • 0

Posted · Report post

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:

attachicon.gifsalesman.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?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Yes. But visit each city only once.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post


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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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 by bonanova
This solution is optimal.
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

152674831?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post


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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.