Depth first search

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).

Various guiding Junctions as criteria to pick the most promising states from W depth-first search, breadth-first search, bounded-width search [21], best-lower-bound search, random search, combined search criteria [22], etc. 

The computational equipment was a 3.06 GHz Xeon machine with 2 GB of main memory and Linux operating system. All tests were limited to five million of visited nodes and this limit was reached in all test runs. The configuration of the waiting list W of TAopt was depth-first search combined with cost minimization. In order to reduce the search effort, the search space was reduced by reduction techniques described in Panek et al. [22] with small modifications. Results of test runs with different initial quantities for So are shown in Table 10.2. The results show the computation times, the numbers of nodes visited to find the solution,... 

Decision Trees provide the overall structure for problem resolution in the current system. The outcome of a test at a particular node in the tree is recorded and directs the next decision for branching. If a failure is encountered at all possible branches, the un-resolved problem is passed back up to the node at which there last existed a possible, untested, solution. Prolog lends itself nicely to this structure since its basic architecture includes decision-making via such a "depth-first" search strategy(2)... 

Third, it is easy to find the components and the decomposition tree. An algorithm for this purpose, which uses depth first search (a systematic method of exploring a graph) has been developed (5 D 55,56) It runs in 0(n+m) time on an n vertex, m edge graph. 

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. 

Tarjan, R. E. Depth-first search and linear graph algorithms. SIAM Journal of the ACM 1972, 22, 146-160. 

The memory capacity of a computer is also taxed by such an organic synthesis program. At present there is no attempt to retain the whole of the synthesis tree. This means we cannot do a breadth first search. If we could do a breadth first search the efficiency of the search would be improved as we would be guaranteed the shortest possible synthetic pathway. (In a depth first search we move from A down to Bf down to C", let us say and so forth. In a breadth first search one generates all the B s, then all the C s and so forth. Each of the searches terminates when an available substance is found. The depth first search is constrained in its depth by an instruction from the... 

The joint spectral radius approach appeared in a paper by Ingrid Dau-bechies and Jeffrey Lagarias[DaLa91] in 1991, and also in one by Hartmut Prautzsch and Charles Micchelli[PM87] in 1987. Efficient computation is still a hot topic. A strong competitor for the ideas described in section 18.3 above is the depth first search method developed by the team of Ulrich Reif. 

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. 

Control Structure. The rules are invoked in a backward-chaining scheme that produces a depth-first search—that is, the inference engine tries to satisfy a goal by evaluating all rules that lead to that goal. Heuristic rules were used as much as possible to shorten the search. For example, the system may ask the user to select the desired response action, either containment or treatment of the wastes. If the user chooses containment, rules for treating the main wastes will not be activated. If by-products of the containment technologies require treatment, however, rules for treatment will still be explored. 

---