Breadth-first algorithm

AIDES uses this look ahead, scoring, and then making of all match decisions at once as its way of developing the better flowsheets. It can be viewed as a breadth first algorithm therefore. From the evidence, it is not yet possible to say which approach is better, that used by AIDES or that by BALTAZAR. Of interest is that two such different approaches exist, and both seem to get reasonable structures. 

The branch and bound BB approaches start by solving the continuous relaxation of the MINLP and subsequently perform an implicit enumeration where a subset of the 0-1 variables is fixed at each node. The lower bound corresponds to the NLP solution at each node and it is used to expand on the node with the lowest lower bound (i.e., breadth first enumeration), or it is used to eliminate nodes if the lower bound exceeds the current upper bound (i.e., depth first enumeration). If the continuous relaxation NLP of the MINLP has 0-1 solution for they variables, then the BB algorithm will terminate at that node. With a similar argument, if a tight NLP relaxation results in the first node of the tree, then the number of nodes that would need to be eliminated can be low. However, loose NLP relaxations may result in having a large number of NLP subproblems to be solved which do not have the attractive update features that LP problems exhibit. 

Fig. 3.2 Schematic of the CATS descriptor calculation, (a) The hydrogen-depleted two-dimensional molecular graph provides the input, (b) The graph is simplified for the distance matrix computation different bond orders are not considered (unweighted graph) and all element types are disregarded. The algorithm starts at an arbitrary chosen atom and visits all nodes of the graph in a breadth-first manner, thereby building up the distance matrix. The numbers at the vertices are used to reference individual atoms in the distance matrix.

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

If we require that the estimate underestimates the actual costs of the remaining path segment then we can prove that the A algorithm always finds a cheapest path. If the estimator is always zero, then the path search amounts to a normal breadth-first traversal of the graph (Russell Norvig, 1995). 

Two samples were obtained for each reachability problem by conducting a breadth-first and depth-first search exploration. We compared the results of both algorithms to know which one conducts a better exploration toward markings with same cardinality as the target marking. 

Tables 1.1 and 1.2 have the results of some explorations of the SSp for markings with certain cardinality, using the breadth-first (upper result) and depth-first (lower result) algorithms.

---