Optimal Stopping in a Discrete Search Problem

In a search among m locations for an object possibly hidden in one, we are given prior probabilities of location p_i, searching costs c_i, and overlook probabilities α_i. It is known also that an “unsearchable” location contains the object with prior probability p₀, and, in addition, a penalty cost C is charged if the search is terminated unsuccessfully. Although an optimal search strategy for the problem is known, the best stopping rule is not. Under a certain constraint on C, independent of the prior probabilities p_i, the optimal stopping rule is shown to be determined by the optimal m-stage look-ahead strategy.