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 as follows:

1. 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.
2. No pruning is done within TOPSAVE levels of the root.
3. 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 SDSAVE option.
4. All other levels are reduced in number by a factor of the REDUCTION option.

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:

PRTFRQ

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.

LIMIT

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.

REDUCTION

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.

TOPSAVE

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.

SDSAVE

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.