4
$\begingroup$

Let's assume I am trying to find a hidden treasure.

The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is an integer). In order to find the treasure I have to take with me a detector. The detector can spot the treasure only if it is above it.

My starting position is the 0 point and I can move back and front until I cross the treasure, so that my detector can track it. I am always moving on the integer line. Which is the most efficient way to move through the axis in order to track the treasure?? I have to find an algorithm that allows me to find the treasure by covering a distance $O(|x|)$

My approach: After some consideration, I think that the most efficient way to find the treasure is the following: Starting from 0 I move front until I reach number $2$. Then I move back until I reach number $-2^2$. Then I move front until I reach number $2^3$. Then I go back again until I reach number $-2^4$ and so on...

However, I am having difficulties on proving that there is a constant $c$ (for which I have to calculate an upper bound) so that my algorithm is going to help me find the treasure at $c |x|$ moves at most. Any help is much appreciated! Thanks in advance!

P.S. I am new at the computer science stack exchange so I am not sure about the tags. Correct them or add more if necessary.

$\endgroup$
  • 1
    $\begingroup$ @narekBojikian Thanks for the response! I am still a bit confused. Could you provide a more extensive answer? $\endgroup$ – MJ13 Oct 26 '19 at 19:20
  • 1
    $\begingroup$ @narekBojikian Yeah I got that! It would be really helpful if u could write down a more analytical answer! Thanks again! $\endgroup$ – MJ13 Oct 26 '19 at 19:27
  • 1
    $\begingroup$ My comments were not well formulated that is why I deleted them but you can find the full answer now $\endgroup$ – narek Bojikian Oct 26 '19 at 19:52
  • 1
    $\begingroup$ This is known variously as the lost cow problem, the cow-path problem, and similar names. It’s a standard example in the field of online algorithms. You can find a lot of pertinent material online. $\endgroup$ – Yuval Filmus Oct 26 '19 at 22:37
  • $\begingroup$ @YuvalFilmus Didn't know that! Your referrence helped a lot. Thank you! $\endgroup$ – MJ13 Oct 27 '19 at 9:32
3
$\begingroup$

Your problem is known variously as the lost cow problem or the cow-path problem, and is a standard example in online algorithms. The algorithm you describe is 9-competitive, which is optimal for deterministic algorithms. For randomized algorithms the competitive ratio is roughly 4.6. See for example a writeup apparently by Rudolf Fleischer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So 9-competitive algorithm means that the constant $c$ that i need to upper bound is 9 right? $\endgroup$ – MJ13 Oct 27 '19 at 10:16
  • $\begingroup$ Right, that’s what it means. $\endgroup$ – Yuval Filmus Oct 27 '19 at 10:17
  • $\begingroup$ So, the proof of the Theorem 2 in the following link: citeseerx.ist.psu.edu/viewdoc/…) shows that the algorithm is 9-competitive and solves my problem, right ? $\endgroup$ – MJ13 Oct 27 '19 at 14:13
  • $\begingroup$ Yes. And the following theorem shows that "9" is optimal. $\endgroup$ – Yuval Filmus Oct 27 '19 at 16:51
  • $\begingroup$ Yeah I see..And I could also use the notation $|x|$ instead of $x$ at the proof since we use the distance from 0 and we dont care about the actual position of x (positive or negative) right? $\endgroup$ – MJ13 Oct 27 '19 at 17:31
2
$\begingroup$

I will suggest a similar strategy. Note that your strategy yields a constant factor better than the one presented here but the proof is more technical.

Let us divide the strategy in rounds $1, 2, \dots$, where in round $i$ we go $2^{i-1}$ steps to the right, then we go back to the center and we repeat the exact same to the left. This means we go one step to the right then back to the middle and one to the left and back again then two to the right and two to the left then 4 to the right and so on. The total number of steps is upper bounded by

$$4\sum\limits_{i=0}^{\left\lceil \log x\right\rceil} 2^i$$ $$\leq 4 \sum\limits_{i=0}^{\log x + 1} 2^i$$ $$\leq 4\sum\limits_{i=0}^{\log (2x)} 2^i$$ $$\leq 4 \cdot 2^{\log(2x)+1}$$ $$= 4\cdot 2^{\log(4x)}$$ $$= 16x,$$ where the factor 4 in the first line means going to the right $2^i$ steps then back to the center and repeating on the left side.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer! Which is the total number of steps i have to follow in this case? (which has the upper bound you mentioned) Is it $$1+1+1+1+2+2+2+2+4+4+4+4+... = 4\sum\limits_{i=0}^{\left\lceil \log x\right\rceil} 2^{i}$$ ?? $\endgroup$ – MJ13 Oct 26 '19 at 20:05
  • $\begingroup$ Yes exactly, and you stop when you find it. Note that for any number x there is an exponent of 2 not less than x but less than 2x. $\endgroup$ – narek Bojikian Oct 26 '19 at 20:11
  • $\begingroup$ Mathematically speaking, for any positive integer $x$ there is a non-neg. integer $k$ such that $x \leq 2^k < 2x$ $\endgroup$ – narek Bojikian Oct 26 '19 at 20:13
  • 1
    $\begingroup$ The truth is that I am a beginner on this field and as a result I am not familiar with this kind of problems and their mathematical background. Your solution was very helpful and easy to follow. However, even if I tried, I can't calculate an upper bound for my own algorithm, which was my initial question. If u could do the math in this case I would be really grateful and I will accept the answer as well. In either case thank you very much for your time! $\endgroup$ – MJ13 Oct 27 '19 at 7:28
  • 1
    $\begingroup$ After some search I found this article: citeseerx.ist.psu.edu/viewdoc/… . I think that the proof of Theorem 2 is what I am looking for. The constant $c$ that we were talking about seems to take the value 9. The lower bound seems more complicated. However, the upper bound is what I care about. $\endgroup$ – MJ13 Oct 27 '19 at 9:29
0
$\begingroup$

Your approach is correct. Without loss of generality, suppose that $2^{2n-1} < x \le 2^{2n+1}$. Now, if you count the number of steps needed to find $x$ with your algorithm, you'll find out that it contains the sum of geometric progression which can be bounded by $2^{2n+3} = 16\cdot 2^{2n-1} = O(x)$ since $2^{2n-1} < x$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your response!Which is the exact number of steps needed to find x ? (that has the upper bound you mention) $\endgroup$ – MJ13 Oct 26 '19 at 20:09

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.