Breadth-first search

In this case, the breadth first search yields the optimum with a fewer number of nodes to be searched. Different search strategies than the ones used here can readily be used10. It is likely that different problems would be suited to different search strategies. 

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. 

Sequence through the elements of IP(G) in any order, chaining up the partial ordering for each element. Beginning with the last element of IP(G) a breadth-first search is required and if an unmarked element y is encountered which has been reached from all other elements of IP(G), execute ... 

Close matches The close matches are the union of the upward chains from each member of IP(G) (not including supergraphs). In the most obvious implementation of Phase 2, a hash table is used to manage the breadth first search. It contains information about which nodes have been visited and which upward chains they are on. The desired union can be found simply by collecting elements of the hash table. 

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 breadth first search the optimal solution is obtained in node 3 as shown in Figure 5.3, and we need to consider the same number of nodes as in Figure 5.2. 

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. 

Figure 5.3 Binary tree for breadth first search...

J. Figueras. Ring perception using breadth-first search. /.Chem. Inf. Comput. Sci., 36, 986-991, 1996. 

In CHIRP, we have essentially used a forward breadth-first search. This is necessary if our goal is to look at the various product alternatives, any of which could be promoted (or inhibited) by a proper choice of reaction conditions. Today we can vary only the temperature to guage the effect on the free energy of reaction. We hope, however, that CHIRP when completed should be able to suggest other reaction conditions, including catalysts, for a process that converts some known starting materials to some desired products. Care must be taken to ensure that a proper balance is maintained between the empirical constraints inserted to make the system more accurate and the ability to search for a wide range of alternatives. 

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

Whenever the procedure construct-variable-influence-pathways has to generate a number of alternative variable-influence paths, it employs a breadth-first search strategy. The procedure, expand-node, is used to establish the expansion list through the following algorithm ... 

A Symbolic Traversal is a breadth-first search that returns at each iteration the set of states reached from the current state set. 

A customer is considered to be supphed with power if there is at least one unbroken path leading from at least one of the ten in-feed transformers to the network station supplying the customer. A breadth-first search strategy is used to find all nodes that can be reached from at least one transformer. The possible drawbacks of only considering topology are discussed in 4.1. 

Figure 9. Illustration of search-time discovery of reaction sequences. A breadth-first search is used to find a pathway of molecules linking the reactant hit list to the product hit list...

Figure 1 A breadth first search through the state space of the 8 puzzle ...

Perform a breadth-first search until a ring is found (use a queue to improve efficiency)... 

---