3
$\begingroup$

I'm thinking about the following strategy for Fastest way to collect an arbitrary army:

  1. When a soldier decides to go to some house he "reserves" it.
  2. 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}$?".

| improve this question | |
$\endgroup$
5
$\begingroup$

No I don't think that strategy works.

enter image description here

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I'm just pleased to see that you figured it out on your own. I'd already considered this strategy but had eliminated it. This is why you need a more "space filling" algorithm than a "house filling" algorithm as houses are arbitraily small. $\endgroup$ – kaine Jun 6 '14 at 13:45
  • $\begingroup$ So probably we can conclude that any purely "house filling" algorithm will not work. And The algorithm Must have (at lease several) directions like "go to the point (0.75,0.5)". What do you think? $\endgroup$ – klm123 Jun 6 '14 at 14:20
2
$\begingroup$

Yes, there is.

Let's consider a spiral, the distance between neighbouring turns being 0.25. Houses are placed along the spiral in groups, the distance between groups being 0.125. Each group (starting from the centre) has twice as many houses as the previous one.

It is easy to show that the soldiers will go consecutively from one group to another. So the path will take $2*0.25+2*0.5+2*0.75+3*1+\sqrt{0.5} = 6.7 > 2+\sqrt{2}$.

enter image description here

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.