Skip navigation
Skip navigation

Estimating search tree size

Kilby, Philip; Slaney, John K; Thiebaux, Sylvie; Walsh, Toby


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 chronological 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...[Show more]

CollectionsANU Research Publications
Date published: 2006
Type: Conference paper
Source: Proceedings of The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference


File Description SizeFormat Image
01_Kilby_Estimating_search_tree_siz_2006.pdf478.05 kBAdobe PDF    Request a copy
02_Kilby_Estimating_search_tree_siz_2006.pdf1.66 MBAdobe PDF    Request a copy
03_Kilby_Estimating_search_tree_siz_2006.pdf319.27 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator