Discrete Search with Directional Information

Donald A. Berry and Roy F. Mensch
Additional contact information
Donald A. Berry: University of Minnesota, Minneapolis, Minnesota
Roy F. Mensch: Prudential Insurance Company, Newark, New Jersey

Operations Research, 1986, vol. 34, issue 3, 470-477

Abstract: 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 ; the cell containing the object if i = N and the cell does not wink; and no 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.

Keywords: 751 search and surveillance; 793 Bayesian statistics (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.34.3.470 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:34:y:1986:i:3:p:470-477

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().