Optimal versus randomized search of fixed length words
Helmut Prodinger, W. Szpankowski · 2003
A combinatorial search problem can be defined as follows: Given a set W={w /sub 1,/ w/sub 2/,..., w/sub m/} of m words over a (binary) alphabet /spl Sigma/, design a sequence of tests that successfully find the word w* /spl isin/ W being sought. The prime goal of the optimal search is to find the sought word w* with the smallest maximum or average search time. Here, we deal with a randomly selected set W of m binary words of fixed length n, that is, the set W={w/sub 1/,... w/sub m/} is chosen with equal probability among all possible subsets of size m.