( ) ( ))
1 If there are man prefi es whose cost is higher than the cost of the minimal ordering, then best first search saves time.   ut if the number of such prefi es is small, using best first ss priorit   ueue, according to its cost.

sample run of lgorithm will be shown later (in ection 7).

## 4. The Divide-And-Conquer Subgoal Ordering Algorithm

lgorithm 1 presented in  ection    is ver  e  cient, but is applicable onl  when the entire set of subgoals is independent. Igorithm can handle a dependent set of subgoals but is ver ine cient. Igonthm , acombination of the two, can e ploit independence of sub goals for better e cienc . owever, the obtained benefit is uite limited. In this section, we present the ivide and on uer ( DAC ) algorithm, which is able to e ploit subgoal inde pendence in a more elaborate wa . The algorithm divides the set of subgoals into smaller ssseesssss

## 4.1  Divisibility  Trees Of Subgoal Sets

In this subsection we define a structure that represents all the wa s of breaking a subgoal set into independent parts. ur algorithm will work b traversing this structure.

Definition: et and be sets of subgoals. The divisibility tree of under a tree defined as follows is an  N
),

( leaf( , ) is independent  under DTree( , ) =   OR( , , DTree(    Bi ,     Bi )  Bi E    )     is indivisible under ( AND(  ,  ,  DTree( i,  )    i E DPart( ,  )  ) is divisible under
ach node in the tree ( o   o) has an associated set of subgoals (  )      o and an associated binding set  (  )      o.  or the root node,  (  )     o.  (  )     o. If the binding set of the root is not specified e  plicitl , we assume it to be empt .   or   N    nodes nodes we also define the sets of children.

and If ( ) is independent under ( ), then is a leaf.

If (  ) is  indivisible under  (  ), then     is an       node.    ach subgoal      in   (    ) defines a child node whose set of subgoals is the body and the binding set is ing elcally i the binder of the generated child. Note that the binding set of ever node in a divisibilit tree is the union of the binders of all its indivisible ancestors and of the root s binding set.

If ( ) is divisible under ( ), then is an N node. ach subset in the divisibilit partition ( ( ) ( )) defines a child node with associated set of subgoals i and binding set ( ). ivisibilit partition was defined in ection . .1.