0
$\begingroup$

You are standing on the middle of a East-West street. A row of closed doors in front of you, and you have a key on hand which can only open one specific door. Compose a strategy so that X/N value is smallest under the worst situation. X is the distance you covered when arriving at the correct door. N is the distance between the door and the original point.

  • 0
    Compose a strategy for _what_?2012-01-29

1 Answers 1

2

Your problem is known as the cow-path problem. The answer is an example of an online algorithm. The best $X/N$ is known as the competitive ratio. The competitive ratio in your case is~$9$ for deterministic algorithms, and $4.6$ for randomized algorithms.

See Wikipedia for references.

  • 0
    Link to that instead.2012-01-29