Tree Size by Partial Backtracking
1978; Society for Industrial and Applied Mathematics; Volume: 7; Issue: 4 Linguagem: Inglês
10.1137/0207038
ISSN1095-7111
Autores Tópico(s)Data Visualization and Analytics
ResumoKnuth [1] recently showed how to estimate the size of a backtrack tree by repeatedly following random paths from the root. Often the efficiency of his method can be greatly improved by occasionally following more than one path from a node. This results in estimating the size of the backtrack tree by doing a very abbreviated partial backtrack search. An analysis shows that this modification results in an improvement which increases exponentially with the height of the tree. Experimental results for a particular tree of height 84 show an order of magnitude improvement. The measuring method is easy to add to a backtrack program.
Referência(s)