Optimal depth-first strategies for and-or trees
Russell Greiner, Ryan Hayward, Michael S. O. Molloy · 2002
A probabilistic boolean expression (PBE) consists of a boolean expression over a set of boolean variables, each with a corresponding cost and probability value that indicates respectively the cost of determining a variable's value and the probability that the value is true. Given a PBE, a resolution strategy is a sequential testing algorithm that determines the value of the expression, where each test is a query of the value of one variable. A strategy is optimal if its expected cost is minimum, over all possible strategies. The minimum cost resolution strategy problem (MRSP) is to find an optimal strategy of a given PBE. As MRSP is NP-hard in general, we consider the restricted case in which each variable occurs exactly once; the corresponding expressions are sometimes called and-or trees, since they have a tree representation in which internal nodes correspond to (boolean) operators and leaf nodes correspond to variables. We further assume that variables are independent, and focus on a depth-first algorithm, dfa, that orders subexpressions within subtrees based on probability/cost ratios. Our main results are that dfa produces optimal strategies for and-or trees with depth 1 or 2, but can be very bad for and-or trees with depth 3 or more.