OPTIMAL SEQUENTIAL FILE-SEARCH - A REDUCED-STATE DYNAMIC-PROGRAMMING APPROACH

This paper continues the study of a file search problem in 1994 by Mon ahan. The objective is to determine whether or not a record is in a se quential file whose contents are initially unknown. Costly information regarding the contents of positions within the file can be purchased. The problem of determining an optimal search and disposition strategy is formulated as a Markov decision process whose state space is polyn omial in the number of possible records in the file. As a result, the computational effort required to determine transition probabilities an d expected payoffs is also polynomial.