I'm thinking about the following strategy for Fastest way to collect an arbitrary army:
- When a soldier decides to go to some house he "reserves" it.
- Once a soldier is free (has delivered the news to another house) he takes the closest house from all unreserved and goes there. If there are several closest houses he chooses at random.
My question is "Is there a house placement example for which this strategy gives a time bigger than $2+\sqrt{2}$?".
Answer
No I don't think that strategy works.
If we consider a clusters of very close houses such that every house will be reserved before they are reached, it is easy in imagine arbitrarily long paths like the one in the top left of my picture. The arrangement in the diamond would fail yours but pass mine. Each number represents a very dense arrangments of that number of houses. At least 1 house will not be reached before your due date much less get back to the castle.
No comments:
Post a Comment