0
$\begingroup$

There is an arbirarly long line of unknown size. You are standing at a particular point you can either move 1 step forward or 1 step backward. You have to search for an object in that line. Your object can be in any direction. Give an optimal solution.

A search might be 1 step forward, 2 back and so on.

Can you do better than that? What would be an efficient search pattern?

$\endgroup$
  • 1
    $\begingroup$ arbirarly long line of unknown size Do you mean a finite segment? $\endgroup$ – dxiv Dec 2 '16 at 3:26
3
$\begingroup$

I don't have a proof, but strongly suspect it will be hard to beat going to one end of the segment, then turning around and going to the other end. A good measure of efficiency is the total number of steps taken over all the possible locations of the object. If you are $a$ from the end in the direction you start out and $b$ from the other end this results in $\frac 12a(a-1)+2ab+\frac 12b(b-1)$, with the first term representing the sums of the distances in the direction you start out, the $2ab$ being the $b$ cases of going $a$ to one end and $a$ back, and the last term the sum of the distances after you get back to start. You did not specify your strategy after the first three steps, but you have already had one case where you know you will not find the object and presumably have two more to come after you turn around again.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So you believe this would out perform a bounds doubling strategy like this one? $\endgroup$ – candied_orange Dec 2 '16 at 4:03
  • $\begingroup$ In the problem you link to there is no definition of an optimal solution. I have given a definition and a calculation of how my algorithm performs. I suggest you calculate how the competing algorithm performs and compare it. If you just think about how many steps get retraced you may see the reason I suggested the one I did. In the one you link to they specify an infinite line, which means you cannot assume a uniform distribution for the object location. Your question seemed to suppose a finite line of unknown length, so I worked with that. In that case a uniform distribution makes sense $\endgroup$ – Ross Millikan Dec 2 '16 at 4:08
  • $\begingroup$ I'm satisfied with the simple reasoning of going over already troden ground is a waste when performed once let alone multiple times. I'm asking because I've been suprized before. I see this pattern holding regardless of the length of the line. $\endgroup$ – candied_orange Dec 2 '16 at 4:32
  • $\begingroup$ Regardless of the distribution would it ever make sense to go back over explored ground? $\endgroup$ – candied_orange Dec 2 '16 at 4:32
  • $\begingroup$ You have to if you want to get to unexplored ground since you probably start in the middle. You just want to do it as little as possible. $\endgroup$ – Ross Millikan Dec 2 '16 at 4:52

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.