12.4.6 Search Tree Pruning Options
The TREE global option is used to control the pruning and display
of the search tree. When directed searches are performed one large
problems, see Overview of Directed Searching, the search tree can
grow very rapidly, and consume all available virtual memory. Generally,
one is not interested in running these searches to completion, so
removing open nodes that are not likely to be expanded is an appropriate
step to conserve memory. Depending on the search strategy, the method
used for pruning the tree will vary.
In the case of the evaluation directed search strategy, the tree pruning
strategy is obvious, the nodes with the highest evaluations are deleted.
In the deepening evaluation strategy, the tree pruning strategy is much
less clear. Depending on the nature of the degree of freedom, the number
of open nodes at each level may vary substantially. Only those levels
with many nodes should be pruned. In addition, since the top level nodes
are visited most often through the search, these levels should not be
pruned. The specific strategy for the deepening evaluation strategy is
- The average and standard deviation of the number of open nodes
per degree of freedom is calculated. Only those degrees of freedom that
have more than one open node are used in the calculation.
- No pruning is done within TOPSAVE levels of the root.
- No pruning is done where the number of nodes on a level is less than or equal
to the average number minus the standard deviation times the value of the
- All other levels are reduced in number by a factor of the REDUCTION
In the case of the mixed strategy, the program applies both pruning strategies
and deletes only those nodes that satisfy both rules.
The meaning of each option is given below:
- The printing frequency for printing a display of search tree in units of
generated nodes. If the frequency is set to 0, then no printing will be done.
The default is 0.
- When the number of nodes in the search tree exceeds LIMIT, pruning
is done. The default is 10000 for directed searches and 1000 for depth first and
breadth first searches.
- The reduction factor for pruning. When evaluation directed searching
is used, the number of nodes will be reduced by this factor. When
deepening evaluation directed searching is used, those levels in the
search tree that pass their tests will be reduced by this factor. When the
mixed strategy is used, then only those nodes that would have been pruning
by both strategies will be pruned. The default is 3.0.
- The number of levels closest to the root node
that are not pruned when the deepening evaluation directed
search or the mixed strategy are used. The defaults is 1.
- When the deepening evaluation directed strategy is used, only those levels
whose number exceeds the average minus SDSAVE times the standard deviation
of the number distribution will be considered for pruning.
The default value of SDSAVE option is 0.5.