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.

## Question

## bonanova 85

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.

## Link to post

## Share on other sites

## 6 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.