Approximately optimal one‐dimensional search policies in which search costs vary through time
Brian Gluss · Naval Research Logistics Quarterly · 1961
Abstract Consider a model in which there are N neighboring cells in one of which there is an object that it is required to find. The a priori probabilities of the object being in cells 1, …, N are p1, …, pN respectively, and the costs of examination of these cells are tl, …, tN respectively; the search policy is considered to be optimal when the statistical expectation of the total cost of the search is minimized. For the case in which the ti†s are constant throughout the search, an optimal policy solution has previously been found by Bellman and by Smith. In the present paper it is assumed that the costs comprise a travel cost dependent upon the distance from the last cell examined, in addition to a fixed examination cost: initially, assuming that the searcher is next to cell 1, ti = i + t, where t is constant; and from then onwards, assuming that the jth cell has just been examined, ti = | i ‐ j | + t. An optimal search strategy is found in the case where the pi† s are all equal, and approximately optimal strategies in the case where pi is proportional to i. The latter case has application to defense situations where complete searches occur at successive intervals of time, and hence the enemy objects are thinned out the nearer they come to the defense base.