Salesman in a Square

[bonanova]

Al made sales calls at a number of cabins, which lay in a square field, one mile on a side. He drove his car to the first cabin, then visited the remaining cabins and returned to his car on foot, walking several miles in the process. If Al had had a map and perhaps a computer, he could have picked the shortest route to take, (traveling salesman problem). Lacking these amenities, Al simply chose to visit (after the first one) the (un-visited) cabin closest to his current location.

If there were 6 cabins in all, how might they be placed, so that using Al's nearest-neighbor algorithm, and selecting the worst initial cabin, Al would be forced to walk the greatest distance; and what is that distance?

Examples:

2 cabins: diagonal corners, starting at either: 2 x sqrt(2) = 2.828... miles.
3 cabins: any three corners, starting at any of them: 2 + sqrt(2) = 3.414... miles.

Check out n=4 and n=5 as a warm-up.

 

[tojo928]

Think I have the ideal solution here

  Reveal hidden contents

A (0,0); B (1,0); C(1,1); D (0,1); E (cos(30),sin(30)); F (cos(60),sin(60))

This solution assumes if you are excatly the same distance from points you get to choose. Very slight tweaks to the points can force the longest path

Start at A. B,D,E&F are all 1 mile away so pick E (+1 mile)

At E. B and F are both same distance away (2 sin(15)~.5176) so pick B  (+.5176 mile)

At B. A,E,&F are all 1 mile away so pick F (+1 mile)

At F, D is closest (2 sin(15)) (+.5176 mile)

At D, C is closest (+1 mile)

At C, return to A (2^.5~1.414

Total distance walked= 3*(1)+2*(2sin(15))+2^.5~5.449

 

 

[DejMar]

 

  Reveal hidden contents

 

My intuitive placement and path of the cabins would be thus:
Let the vertices of the square be A, B, C, D with the diagonals being AC and BD.

Let the first cabin [a] be at point A.
Let the second cabin be a walk of 1 mile from A along the diagonal AC.
Let the third cabin [c] be perpendicular to diagonal AC on side CD.
Let the fourth cabin [d] be at or on toward point D at no less distance than point C from cabin ;
this should be approximately 0.4 miles distant from cabin [c].
Let the fifth cabin [d] be at point C.
Let the sixth cabin [e] be at point B.
Finally, a return to the car at cabin [a], point from cabin [e] A requires another walk of 1 mile.
Accumulative walk is approximately 4.8 miles.

 

 

[bonanova]

  On 4/7/2018 at 4:53 PM, DejMar said:

 

  Reveal hidden contents

My intuitive placement and path of the cabins would be thus:
Let the vertices of the square be A, B, C, D with the diagonals being AC and BD.

Let the first cabin [a] be at point A.
Let the second cabin be a walk of 1 mile from A along the diagonal AC.
Let the third cabin [c] be perpendicular to diagonal AC on side CD.
Let the fourth cabin [d] be at or on toward point D at no less distance than point C from cabin ;
this should be approximately 0.4 miles distant from cabin [c].
Let the fifth cabin [d] be at point C.
Let the sixth cabin [e] be at point B.
Finally, a return to the car at cabin [a], point from cabin [e] A requires another walk of 1 mile.
Accumulative walk is approximately 4.8 miles.

Not a bad result.

  Reveal hidden contents

The locations (four corners, side and circular arc) are all correct. But adjusting the last two a bit, and changing the first cabin, in order to alter the sequence, the distance can exceed 5.

 

Expand  

 

[DejMar]

Modified solution:
 

  Reveal hidden contents

Let the following lettered points also be the labels of the six cabins. Let the vertices of the SQUARE be AEDF.
Let the midpoint of DF be C. Let B be the midpoint between CE.

The first leg would be approximately 0.83 miles from cabin A to B.
The second leg would be approximately 1.12 miles from B to C.
The third leg would be 0.50 miles from C to D.
The fourth leg would be 1.00 mile from D to E.
The fifth leg would be approximately 1.41 miles from E to F.
The sixth leg would be 1.00 mile from F to A.

The leg-journey will be approximately 5.83 miles.

 

[DejMar]

Correction to modified solution. (It appears I incorrectly calculated the second leg's length by failing to divide it by 2, and my approximation of the first leg also needed adjusting.)

 

  Reveal hidden contents

The lengths of each leg of the salesman's path should be as follows:
Cabin A to Cabin B = (√(13)/4) miles.
Cabin B to Cabin C = (√(5)/4) miles
Cabin C to Cabin D = 1/2 mile
Cabin D to Cabin E = 1 mile
Cabin E to Cabin F = √(2) miles.
Cabin F to Cabin A = 1 mile.
Total length of the salesman's journey: approximately 5.37 miles.

 

Edited April 9, 2018 by DejMar
correcting math

[bonanova]

  On 4/10/2018 at 5:22 AM, tojo928 said:

Think I have the ideal solution here

  Reveal hidden contents

A (0,0); B (1,0); C(1,1); D (0,1); E (cos(30),sin(30)); F (cos(60),sin(60))

This solution assumes if you are excatly the same distance from points you get to choose. Very slight tweaks to the points can force the longest path

Start at A. B,D,E&F are all 1 mile away so pick E (+1 mile)

At E. B and F are both same distance away (2 sin(15)~.5176) so pick B  (+.5176 mile)

At B. A,E,&F are all 1 mile away so pick F (+1 mile)

At F, D is closest (2 sin(15)) (+.5176 mile)

At D, C is closest (+1 mile)

At C, return to A (2^.5~1.414

Total distance walked= 3*(1)+2*(2sin(15))+2^.5~5.449

 

 

Expand  

  Reveal hidden contents

Extremely close to optimal. So close I'm declaring it solved.

  Reveal hidden contents

The best solution I know of has length of L = (5+√2+√5+√6) / 2 = 5.549+ by moving one of your points (E) to the center of side AB and starting by going from that point to B. Check it out.