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]
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.