Search with very limited resources
David Mutchler · University Microfilms International eBooks · 1986
When search resources are highly limited, how should one use acquired information to gain more information? The following probabilistic model (and generalizations of it) is employed to investigate this question in the context of least-cost path algorithms. The arcs in a complete binary tree have value 1 with probability p and 0 otherwise. A scout expands n arcs on the frontier of the search, each time learning the (randomly assigned) value of the expanded arc. After the n arc expansions, a leaf must be selected with no further guidance. What arcs should the scout expand, given that he or she wishes to minimize the expected sum of the arcs along the path from the root of the tree to the selected leaf? Clearly, the final leaf selection should be any leaf below the frontier node (beta) that minimizes the sum of the arcs to the mode (beta) plus p times the distance from (beta) to the bottom of the tree. Let the greedy policy denote the search strategy that employs an analogous rule for selecting the arc to be expanded. The following bad and good news is shown under the assumption that the depth of the tree is at least n. (Search resources are very limited.) Bad news: no matter how many arc expansions remain, if p is large enough, the greedy decision is not the optimal decision from certain situations that may arise naturally. Good news: for p (LESSTHEQ) 1/2, the greedy policy is an optimal search strategy; for 1/2 < p (LESSTHEQ) .682, the expected score of the greedy policy is within a constant of the optimal expected score. Strong evidence--both theoretical and empirical--is supplied that the latter statement holds for all values of p.