Search tree-structured

Figure 6-3. Search tree of mappings obtained by applying the backtracking algorithm for the pair of structures Cq and Qt (see the graphs in Figure 6-2). Array (M, M2, Mj, M4) denotes the mapping 1 —> M, 2 —> M2, 3 —> M3, 4 —> M4.

More generally, MILPs are solved with branch and bound algorithms, similar to the spatial branch and bound method of the previous section, that explore the search space. As seen in Fig. 3-61, binary variables are used to define the search tree, and a number of bounding properties can be noted from the structure of (3-110). 

Fastsearch Index. Term used in MDL databases for a tree-structured index of all the structures in the database. The nodes in the tree represent increasingly complex substructures or properties, where all the structures at or below a given node have in common. The fastsearch index can be very large, but it makes possible very rapid substructure searching. 

As shown in Fig. 7, atom 1 in structure 1 is first tried to be matched onto atom 2 in structure 2. Following this search branch, a substructure with five atoms and four bonds is found before any backtracking is performed (bold lines in structures 1 and 2 of Fig. 7). The size of the common structure found so far is used as a backtrack condition. With this backtracking condition, no branches were cut off before the next more extended substructure containing six atoms and five bonds is found. Then, this new best number of bonds is used as a new backtrack condition for further search. It can be easily seen from structures 1 and 2 in Fig. 7 that the correct MCSS will not be found until atom 1 in structure 1 is matched against atom 8 or 9 in structure 2. This example reveals that most CPU time is wasted on investigating many useless searches on bad branches within the search tree. 

Wipke WT, Rogers D. Tree-structured maximal common subgraph searching. An example of parallel computation with a single sequential processor. Tetrahedron Comput Methodol 1989 2 177-202. 

---