On Self-Organizing Sequential Search Heuristics

This paper examines a class of heuristics for
maintaining a sequential list in approximately 
optimal order with respect to the average time required
to search for a specified element, assuming that 
each element is searched for with a fixed probability
independent of previous searches performed.  The 
"move to front" and "transposition" heuristics are shown
to be optimal to within a constant factor, and 
the transposition rule is shown to be the more efficient
of the two. Empirical evidence suggests that 
transposition is in fact optimal for any distribution of search probabilities.

CACM February, 1976

Rivest, R.

searching, self-organizing, list-processing, heuristics

3.74 5.25

CA760202 JB January 5, 1978  9:44 AM

2885	5	2885
2885	5	2885
2885	5	2885
3061	5	2885
2885	6	2885