Tuesday, June 27, 2017

mathematics - Does this strategy work?


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}$?".



Answer



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.


No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...