Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs

A new method based on a stratified sampling approach, which is called heuristic sampling, is a generalization of Knuth’s original algorithm for estimating the efficiency of backtrack programs and can produce significantly more accurate cost estimates for commonly used tree search algorithms.

Abstract

Determining the feasibility of a particular search program is important in practical situations, especially when the computation involved can easily require days, or even years. To help make such predictions, a simple procedure based on a stratified sampling approach is presented. This new method, which is called heuristic sampling, is a generalization of Knuth's original algorithm for estimating the efficiency of backtrack programs. With the aid of simple heuristics, this method can produce significantly more accurate cost estimates for commonly used tree search algorithms such as depth-first, breadth-first, best-first, and iterative-deepening.