IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v34y1986i3p470-477.html
   My bibliography  Save this article

Discrete Search with Directional Information

Author

Listed:
  • Donald A. Berry

    (University of Minnesota, Minneapolis, Minnesota)

  • Roy F. Mensch

    (Prudential Insurance Company, Newark, New Jersey)

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.

Suggested Citation

  • Donald A. Berry & Roy F. Mensch, 1986. "Discrete Search with Directional Information," Operations Research, INFORMS, vol. 34(3), pages 470-477, June.
    • Handle: RePEc:inm:oropre:v:34:y:1986:i:3:p:470-477
    DOI: 10.1287/opre.34.3.470
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.34.3.470
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.34.3.470?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ferguson, Thomas S., 1996. "A problem of minimax estimation with directional information," Statistics & Probability Letters, Elsevier, vol. 26(3), pages 205-211, February.
    2. Duvocelle, Benoit & Flesch, János & Staudigl, Mathias & Vermeulen, Dries, 2022. "A competitive search game with a moving target," European Journal of Operational Research, Elsevier, vol. 303(2), pages 945-957.
    3. Hassin, Refael & Sarid, Anna, 2018. "Operations research applications of dichotomous search," European Journal of Operational Research, Elsevier, vol. 265(3), pages 795-812.
    4. Garrec, Tristan & Scarsini, Marco, 2020. "Search for an immobile hider on a stochastic network," European Journal of Operational Research, Elsevier, vol. 283(2), pages 783-794.
    5. Chun, Young H., 2016. "Designing repetitive screening procedures with imperfect inspections: An empirical Bayes approach," European Journal of Operational Research, Elsevier, vol. 253(3), pages 639-647.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:34:y:1986:i:3:p:470-477. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.