Ames Laboratory, Department of Energy, ISU, Ames, Iowa

Modeling as a Search Problem

Consider the set of all possible expressions that can be derived from the given set of variables and operations. These can be thought of as a graph with each node representing an expression (Figure 1).

We use the term expression for a node as long as it results in no confusion, since each node can be specified by the expression it represents. The graph G(V, E) can be defined as follows:

1. Each of the given set of variables forms a node in the graph.
2. If two expressions , then
   for every choice of operation op.

We can also think of edges from e₁ and e₂ to the node e₁ope₂. Clearly, this graph represents all possible expressions that can be generated from the given variables and operation types. Note that each node represents a unique expression and the way of generating it starting from the variables can easily be found by following the edges into the node representing this expression. However, two or more expressions could be mathematically equivalent.

The number of operations required to compute any expression in the graph can be found by recursively following the edges coming into the expression. The number of operations for computing e₁ope₂ is 1 more than the operations required for computing e₁ and e₂ except that expressions common to the paths for e₁ and e₂ need be computed only once.

FIGURE 1. Partial search graph for a two-input problem

A set of nodes in this graph whose expressions are mathematically equivalent to the goal expressions constitutes a way of computing the goal expressions with the associated number of operations. The problem then translates to finding the appropriate set of nodes such that the associated number of operations is the minimum over all such possible sets.

Since there is no budget for the number of operations, the graph has an infinite number of nodes. The nodes of the graph can easily be ordered according to the number of operations required to compute the expressions at the nodes. The nodes at level 0 constitute the given set of variables. The nodes at level i consist of expressions that can be computed using exactly i operations. We can easily place a bound on the search since we are interested in minimizing the number of operations. If a known way of generating the goal expressions needs k operations, we need only look at nodes at levels less than k.

Since the graph has a combinatorially explosive number of nodes, it would be impractical to generate and store the graph during the search process. Also, solutions are difficult to identify, since matching subgraphs to the goal expressions (as algebraic equivalents) is itself a combinatorial problem. In order to avoid these problems, it is convenient to do a depth-first search on a tree as shown in Figure 2.

Figure 2. Partial search tree for a two-input problem.

The tree is constructed as follows: The given set of variables forms the first m levels of the tree, one node at each level. The children of node i are all the expressions that can be formed using an operation and any two expressions on the path from the root to node i. The goal is to search for a path in the tree which contains expressions equivalent to goal expressions. Since each node accounts for one operation, paths containing more than the budgeted number of operations need not be explored.