ML Anthology

Estimating Search Tree Size

Philip Kilby, John K. Slaney, Sylvie Thiébaux, Toby Walsh
AAAI 2006 pp. 1014-1019
/aaai/2006/kilby2006aaai-estimating/

Abstract

We propose two new online methods for estimating the size of a backtracking search tree. The first method is based on a weighted sample of the branches visited by chronologi-cal backtracking. The second is a recursive method based on assuming that the unexplored part of the search tree will be similar to the part we have so far explored. We compare these methods against an old method due to Knuth based on random probing. We show that these methods can reliably estimate the size of search trees explored by both optimiza-tion and decision procedures. We also demonstrate that these methods for estimating search tree size can be used to select the algorithm likely to perform best on a particular problem instance.

PDF AAAI Semantic Scholar

Cite

Text

Kilby et al. "Estimating Search Tree Size." AAAI Conference on Artificial Intelligence, 2006.

Markdown

[Kilby et al. "Estimating Search Tree Size." AAAI Conference on Artificial Intelligence, 2006.](https://mlanthology.org/aaai/2006/kilby2006aaai-estimating/)

BibTeX

@inproceedings{kilby2006aaai-estimating,
  title     = {{Estimating Search Tree Size}},
  author    = {Kilby, Philip and Slaney, John K. and Thiébaux, Sylvie and Walsh, Toby},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2006},
  pages     = {1014-1019},
  url       = {https://mlanthology.org/aaai/2006/kilby2006aaai-estimating/}
}