Searching Backtrack

To address issues such as resource contention (i.e., when two different gates attempt to take the same location), one may check for such conflicts during search, backtracking accordingly. Alternatively, such locations may be pre-processed prior to search, so that only one location appears as the candidate of any cell. 

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.

The depth-first search algorithm the backtracking algorithm, respectively) has an exponential order of computational complexity CC [11] CC = 0(b ). The ex-... 

Figure 6-4. Backtracking approach realized as depth-first search aigorithm. Dotted arrows trace the route used for traversing all mappings in the search tree. Each node in the tree corresponds to a mapping between Cq and C-p (Figure 6-2).

In the worst case, the backtracking algorithm will form a search tree of depth n, where n is the number of atoms in the query graph. Also, in this case a separate sub-tree search process for each atom of the target graph will be initiated. That is why the linear multiplier m is apphed to Eq. (7). 

The backtracking algorithm is the core part of every software system that performs substructure searching. There are other approaches which have been applied both as alternatives to the backtracking algorithm or (most usually) in combination with it. Section 6.3.3 describes the approaches used for the optimization of the... 

This backtracking line search tries a = 1.0 first and accepts it if the sufficient decrease criterion (8.78) is met. This criterion is also used in unconstrained minimization, as discussed in Section 6.3.2. If a = 1.0 fails the test (8.78), a safe-... 

The next step is to backtrack up the tree and continue searching through other branches until all nodes in the tree have been fathomed. Another reason to fathom a particular node occurs when no feasible solution exists to the nonlinear problem at node r then all subsequent nodes below node r are also infeasible. 

Figure 5.2 Binary tree for depth first search with backtracking...

The binary trees for (i) depth first search with backtracking and (ii) breadth first search are shown in Figures 5.2 and 5.3 respectively. The number within the nodes indicate the sequence of candidate subproblems for each type of search. 

Using the depth first search with backtracking, we obtain the optimal solution in node 5 as shown in Figure 5.2, and we need to consider 6 nodes plus the root node of the tree. 

At level 1, the lower and upper bounds for the depth first search are (—6.667, +oo) while for the breadth first search are (-6.667, -5). At level 2, the lower and upper bounds for the depth first search are (-6.667, +oo) while for the breadth first search are (-6.667, -6). At level 3, the lower and upper bounds for the depth first search are (-6.5, -5) while for the breadth first search we have reached termination at -6 since there are no other candidate subproblems in the list. When the backtracking begins for the depth first search we find in node 5 the upper bound of -6, subsequently we check node 6 and terminate with the least upper bound of -6 as the optimal solution. 

Once a new X and corresponding trial point x(X) have been determined in a line search iteration, conditions of sufficient progress with respect to the objective function are tested. If these conditions are not satisfied, a new value for X is sought in another line search step of interpolation, following a backtracking strategy (i.e., reduction of X2). 

There is nothing static about the word-key game. The searcher makes up a list which seems to cover his field, and plunges into an index. One word leads to another, such as distillation suggesting fractionation, and he adds a word. A word that looked useful may prove barren, so he shelves it for possible use in another index. Skillful first choices minimize backtracking, but in complicated searches even the seasoned professionals have to retrace some steps through an index now and then. 

We use an Artificial Intelligence technique called the Problem Decomposition Strategy (14, 15) to tackle this problem. We divide the problem of computing a quantity into a number of sub-problems, each involving the computation of a formula with several sub-quantities. When more than one formula is applicable, they are tried one by one. The entire problem space can be represented as an AND/OR tree, and a Depth-first Recursive Search is employed to traverse the tree. The leaf nodes represent quantities whose values are known. The search terminates at the leaf nodes and returns the value to the level above. When a dead-end is reached, the system progressively backtracks to the levels above in an attempt to select smother formula. If the complete search space is exhausted, the system reports that the problem is unsolvable and prompts the user for more information. 

---