Pruning the backtrack tree

Now after backtracking to btl2 atom 11 is marked, whereby atom 7 also becomes unique. Refinement by 11 and then by 7 results in atoms 10,6, and 9 becoming unique in this order. Thus now the partial renumbering scheme is 

Here it is evident, looking at the matrix element (9, 7) T (in italics), that the next discrete pardon to be found, candidate 2, will be better (in the sense of our extremality 

This renumbering scheme is kept as the currently best one. Thereby btl2 is exhausted (Table 5.5), and after backtracking to bill atom 7 is marked, refinement by 7 results in atom 6 becoming unique, so that now the current partial renumbering scheme and partial matrix of bond multiplicities are as follows 

Here matrix element (4, 2) 0 (in italics) determines that all discrete partitions to be derived from this partial numbering will be worse than candidate 2. 

Candidate 2 is thus the basis of the canonical numbering finally obtained as in the previous examples and shown at the bottom of Table 5.5. 

---

Table 5.5. Pruning the backtrack tree for l-azabicyclo[4.3.2]undecane, structure 3 from Figure 5.8. Atoms that become unique are printed in bold.

Therefore this part of the backtrack tree can be pruned immediately. In exactly the same manner the last alternative at btll, marking atom 11 with atom 10 also becoming unique after refinement by 11, is found to be worse than candidate 2. Figure 5.9 shows the backtrack tree corresponding to this example, the pruned parts of the tree are drawn as dashed lines. 

Fig. 5.9. The backtrack tree for structure 3, Figure 5.8. Parts of the tree that are pruned are drawn in dashed lines.

Large parts of the search tree can be pruned in cases of higher symmetry. If two labelings result in the same bond matrix at different positions in the tree, then a symmetry (automorphism) has been found. The information on automorphisms that accumulates in the process finally defines the complete automorphism group of the graph or molecule. This is stored in the form of a set of generators (a Sims chain [93,142,296]). This information is used to prune parts of the backtrack tree found to be equivalent to other parts already considered. 

The combination of the new methods for optimizing and pruning search trees described above, and the backtracking technique, makes the Chen-Robien algorithm a very fast MCSS algorithm. It has become a central mainstay of several other commands within the CSEARCH-NMR database system [69]. 

The backtracking algorithm organizes the search space as a tree where each node corresponds to the application of an operator. At each application, the consistency of the partial structure is evaluated. If consistent, the next operator is applied and the process continues. If inconsistent, this node and attached branches are pruned from the search tree and the algorithm backtracks to the previous node. 

The performance of the original backtracking algorithm can be further improved by pruning-off fruitless branches of a search tree as early as possible. One technique for achieving this was introduced into a backtracking match algorithm by Ullmann in 1976 [16]. 

---