Once the input subgraphs are determined, Hunter-Gatherer begins processing. We will assume the input subgraphs of Figure 31. Below we outline how our solution synthesis mechanism is used to combine results from previous subgraphs in this example. Following this is a detailed example of how the branch-and-bound optimization stage is carried out.
As described above, Freuder introduced solution synthesis as a means to ``gather up'' all solutions for a CSP without resorting to traditional search methods. Freuder's algorithm created a set of two-variable nodes that contained combinations of every two variables. These two variable nodes were then combined into three variable nodes, and so on, until a node containing all the variables, i.e. the solution, was synthesized. At each step, constraints were propagated down and then back up the ``tree'' of synthesized nodes.
Tsang improved greatly on this scheme with the Essex Algorithms. These algorithms assumed that a list of the variables could be made, after which two-variable nodes were created only between adjacent variables in the list. Higher order nodes were then synthesized as usual, starting from the two-variable nodes. Tsang noted that some orderings of the original list would prove more efficient than others, most notably a Minimal Bandwidth Ordering'' (MBO), which seeks to minimize the distance between constrained variables.
HG extends the concept of MBO and carries it to a higher level. The whole concept of synthesizing solution sets one order higher than their immediate ancestors is thrown out. Synthesis, here, is aimed at maximally interacting groupings of variables, of any order. Furthermore, this process of using maximally interacting groupings, or subgraphs, extends to the highest levels of synthesizing. Tsang only creates second order nodes from adjacent variables in a list, with the list possibly ordered to maximize second order interactions. After that, third and higher order nodes are blindly created from combinations of second order nodes. In this work, in a sense, MBO is continued on to the higher levels. The subgraphs of co-constrained variables described in the previous section guide the synthesis process from beginning to end.
One of the main improvement of this approach comes from a recognition that much
of the work in SS-FREUDER and SS-TSANG was wasted on finding valid
combinations of variables which were not related. For example, in the
example worked out in section 2.2, the words ``IBM'' (I), ``Jacob-Smith'' (J) and
``ten-million-dollars'' (T) (among others) are not directly related by any
constraints. Despite this, valid combinations for
are calculated by SS-FREUDER and,
depending on the ordering used, could also be calculated by SS-TSANG.
Furthermore, the SS-TSANG algorithm tends to carry along unneeded
ambiguity. As shown above, if two related variables are not adjacent
in the original list, their disambiguating power will not be applied
until they happen to co-occur in a higher-order synthesis. It should
be noted that Freuder's algorithm does not have this disadvantage,
because all combinations of variables are
created.
The current work
combines the efficiency of Tsang's algorithms with the
early-disambiguation power of Freuder.
For our example, the Tsang algorithm would first use an MBO ordering of the input variables: (G D A ATD C E ESP S). Second order combinations variables adjacent in this list would then be synthesized. G-D, D-A, A-ATD, etc., would be generated at this step. Third order combinations, G-D-A, D-A-ATD, etc., would then be synthesized, and so on, until the eighth order solution containing the entire problem was synthesized. Even if our constraints were of the yes/no variety, enabling a certain amount of pruning at each synthesis, there would still be wasted processing. See section 8.1 for a direct comparison of Tsang's solution synthesis algorithm with our own in contexts where constraints are of this type. The fact is, however, that constraints in semantic analysis are more complex so that straightforward constraint satisfaction and solution synthesis techniques such as those used by Tsang are useless.
In Figure 31, there are only five input subgraphs which guide the synthesis process. The smaller subgraphs, 1, 2 and 3, are processed first. Each is optimized (see section 5.3 for examples) based on the principles in section 3.1. Next, subgraphs 2 and 3 are synthesized into subgraph 4. This involves combining all pairs of plans in subgraphs 2 and 3, as long as those plans are consistent (for instance, if the subgraph 2 plan assigns a value to a variable, the subgraph 3 plan, if it assigns a value to that variable at all, must assign the same value). Subgraph 4 is then optimized, before being combined with subgraph 1 to produce the answer for the whole problem. The bulk of the optimization occurs in the lower order subgraphs which were chosen to maximize this phenomena. Focusing the synthesizer on subgraphs that will maximally optimize produces large savings while still guaranteeing the correct solution.