mith and   enesereth propose performing a best first search in the space of ordered prefi es, preferring prefi es with lower cost. The best first search can be combined with the permutation test and the ad acenc  restriction. In addition, when the subgoals not in a prefi  are independent under its binding, the  can be sorted, and the sorted result concatenated to the prefi .

emma 1 and  orollar  1, this produces the cheapest completion of this prefi .    hen we perform completion, there is no need to perform the ad acenc  or permutation test  if a complete se  uence is  not  minimal, it  will never be chosen as the cheapest prefi even if it is added to the list of prefi es, it will never be e tracted therefrom. The resulting algorithm is shownin igure 7.

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

The advantage of using best first search is that it avoids e panding prefi es whose cost is higher than the cost of the minimal ordering. The polic used b the algorithm ma ,
however, be suboptimal or even harmful.  It often happens that the best completion of a cheaper prefi is much more e  pensive than the best completion of a more e  pensive prefi .

hen the number of solutions is large, it is better to place subgoals with high costs closer to the beginning of the ordering to reduce the number of times that their cost is multiplied.

ore ample, let the set be    (   )   (   )  , with cost(  (   ))    1  , cost(  (   ))    nsols(  (    ))
. Then a minimal ordering starts with the most e pensive prefi nsols(  ))
( ) ( ))
1