부산대학교 도서관

Suppose there are $n$ boxes labelled $1,2,\cdots,n$. Box $s$ may have hidden within it an object. This event, call it $E_s$, has probability $1-p_s$. The events $E_1,E_2,\cdots,E_n$ are independent. A search of box $i$ costs $c_i$ and discovers any object hidden there. Define a strategy $(s(1),s(2),\cdots,s(n))$ to be a permutation of the labels $(1,2,\cdots,n)$. The aim may be to rank the strategies in accordance with the expected costs incurred if the boxes are searched in the order specified by the strategy until either an object is found or all boxes have been searched. \par The authors show how a variety of apparently more complicated sequential optimization problems can be expressed as special cases of the stated elementary search model using ``sufficiently small'' transformation parameters. If the problem's data is integral, bounds for the parameters in question can be given, otherwise more sophisticated algebraic considerations become necessary.