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.
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.
Share this post
Link to post
Share on other sites