<< Prev | - Up - | Next >> |
The `generate and test' method generates complete assignments and only then checks whether they are solutions or failures. We can usually improve on it by interleaving generation and checking: after each choice we can check if any constraint is obviously violated. For example, in our problem the constraints are V1 < V2
, V2 < V3
, ... , V14 < V15
. Thus, as soon as we have guessed values for V1
and V2
, we can immediately check whether V1 < V2
is violated or not; we don't have to wait until values have been guessed for all other variables too. As a result, we can decide failure much earlier and the search tree become much smaller. For the example with only 6 variables, it now contains 631 nodes instead of 93311:
This strategy, often implemented using some notion of coroutines, is traditionally called `test and generate'. The tests are posted first, but each remains suspended until its variables have all been assigned. Generation then proceeds as before, except that a test becomes active as soon as its variables have been assigned and thus may cause failure before further levels of the search tree are generated.
<< Prev | - Up - | Next >> |