

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

![0_image_2.png](0_image_2.png)

We compute the costs of all possible orderings, using Equation 5:

![0_image_3.png](0_image_3.png)

![0_image_4.png](0_image_4.png)

(
The minimal ordering is 
, and this is exacily the ordering which is found much more quickly by Algorithm 1 for the set
:   has the smallest value, l , then goes   with   ( )    , and finally   with
( )
Note that the sorting algorithm re ects a well known principle  The best implementa tions of generate and test programs are obtained with the tests placed as earl as possible in the rule bod and the generations as late as possible (Naish, 19 a).   f course, the cheap tests should come first, while the e pensive ones should come last. If one looks at measure, one uickl reali es that tests should be put in front (because nsols t he 1,
), while generator subgoals should move towards the end (nsols 1, so SO
).

The weakness of the test first principle is in the fact that not ever subgoal can be easil tagged as a test or a generator. If one subgoal has nsols 1 and another one has nsols 1, then their order is obvious even without looking at the costs (because their values have di erent signs).   ut if both subgoals have nsols   1, or both have nsols 1, then the decision is not so simple. orting b can correctl handle all the possible cases.

3.2.3 Correctness Proof of the Sorting Algorithm for Independent Sets ee e are now going to prove that  lgonthm 1 always finds a minimal ordering for independent sets.   irst we ss