PROBLEM LINKSDIFFICULTYHARD EXPLANATIONThe solution can be described in several not really hard steps: 2) Now we remove all NOTs from the tree using the following rules: 3) So after step 2 we have a tree with only AND and OR as inner node. Now we consider those operations to accept more than two operands and merge the nodes of the tree in the following way: AND(E1, AND(E2, E3)) = AND(E1, E2, E3), OR(E1, OR(E2, E3)) = OR(E1, E2, E3). 4) After step 3 we will end up with AND/OR tree: any child of AND node will be a variable or an OR node, and any child of OR node – a variable or an AND node. For such a tree we can recursively calculate the expected amount of evaluations needed to result this node. The best order of evaluation of children can be derived for each node. The answer is the expected amount of evaluations for the root. For the best order of evaluations for some inner node let us consider the following node: X = AND(E1, E2, …, En). If we fix any order of evaluations of children: F1, F2, .. Fn. Then the expected number of evaluations will be: M(X) = M(F1) + P(F1) * (M(F2) + P(F2) * (M(F3) + …)). Let’s look at any two children. If we place Fi before Fj we get [… + M(Fi) + P(Fi) * (… M(Fj) …)], otherwise we get [… + M(Fj) + P(Fj) * (… M(Fi) …)]. So the lesser is the value of this part the better is the order. We have: M(Fi) + P(Fi) * M(Fj) ? M(Fj) + P(Fj) * M(Fj) M(Fi) * (1 – P(Fj)) ? M(Fj) * (1 – P(Fi)) M(Fi)/(1 – P(Fi)) ? M(Fj)/(1 – P(Fj)) That means that in this case we should sort the children by M(E)/(1 – P(E)) to get the best order of evaluations. Similarly can be done for OR nodes. However such approach turns to produce optimal solutions only for certain types of and/or trees. For example, for and/or trees of depths no more than two. Additional information can be found in this paper: http://www.cs.toronto.edu/~molloy/webpapers/aotree.ps SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 23 Nov '12, 16:45
