Heuristic sampling on DAGs

摘要

Many problems in computer applications can in theory be solved by searching through a directed-acyclic graph (DAG). In practice, however, this approach has been hampered by our analytical inability to predict the search cost accurately without actually implementing and executing the program. To overcome this inability, a simple and quick heuristic procedure based on a stratified sampling approach is presented. It generalizes a tree sampling technique already shown to be useful in predicting the performance of tree-searching programs. With the addition of this DAG sampling procedure, we should be able to forecast the complexity and feasibility of alternative tree or DAG searching algorithms so that we may utilize our computational resources more effectively.