Discrete Search with Directional Information
Donald A. Berry, Roy F. Mensch · Operations Research · 1986
An unknown number N of cells are arranged in numerical order. An object is hidden in cell N. The problem is to locate the object—thereby determining N—within n searches. We consider a version of this problem that has applications in several problem settings: locating flaws in a discrete circuit, locating nerve endings, or locating the end of a tree root. A search of a site determines whether a cell is present and contains the object, except that it might overlook, with known probability w, a cell that is present; that is, a cell can “wink.” A search of site i reveals an empty cell if i N or if i ≤ N and the cell winks. Various special cases are considered. We define “bisection strategies” and show that they are optimal when w = 0. When w > 0, we partially characterize optimal strategies when n = 2, and completely characterize optimal strategies when there are at most two cells. For various values of n and w we give tables of the probability of finding the object for three intuitively reasonable strategies.