Consider the following one-dimensional version of the game battleships. There is a battleship somewhere on $\mathbb N$, i.e., a interval $N,\ldots,N+k$. Your task is to find whether this battleship lies in the interval $1,\ldots,n$ using the minimal number of tests (on can ask if the battlship includes $i$ for any $1\leq i \leq n$). One does not know the value of $k$ (nor a bound on it). The battleship may not be in the test interval at all.
Intuitively I think that one choses a permutation of $\{1,\ldots,n\}$ so that after testing the first $m$, the remaining intervals of untested points in $1,\ldots,n$ are as small as possible. Example: if $n=5$ then $1,5,3,2,4$ would give an optimal strategy, as would $5,1,3,2,4$.
It is easy enough to work out an algorithm to generate such permutations
- maintain a sorted list of intervals, put $[2,n-1]$ in it
- maintain a results array and put $1$ and $n$ on it
- pop the largest interval from the sorted list, divide into two, push the division point onto the results array, push the divided intervals into the sorted list if they are not singletons
For my problem, $n<100$, so the above will probably suffice in terms of performance, but it occurs to me that such permutations might arise in other contexts, and there might be a more efficient way of generating them. Any takers?
Motivation: This arises in a non-convex global optimisation code which uses a "subdivide and reject" method. The battleship is a region around the global maximum, the tests are (rather expensive) function evaluations. If the global maximum is in the region of interest I must subdivide, if not then I can reject. Obviously I want to find whether the global maximum is in the region as soon as possible, since this saves me function evaluations.
[edit]
Thank you for the replies. I think that Douglas Zare's answer points in the right direction. After testing the end points one knows that the target is in the interior of the region (if it is there at all). Then the uniform insertion strategy seems to be the best one (possibly some chages will be needed to handle the integer location of the samples, but I don't think this is a big deal).
Incidentally, I just tested the simple strategy $1,n,2,\ldots,n-1$ on my code (i.e., test the end points, then the interior) and it gives a 2% reduction in evaluations --- well worth having. I will post the improvement with uniform insertion here when it is implemented.