A Wrinkle on Satisficing Search Problems

Abstract

The problem of optimally ordering the execution of independent disjuncts is explored. Only a single answer is sought, not necessarily the best one. By definition, this is called satisfying search. Since the disjuncts are independent, the total combined probability that a solution is found does not depend on the execution order. However, the ordering does affect the total expected execution time because execution ceases as soon as any solution is discovered. Therefore, the optimal ordering is the one that minimizes the total expected work. The new result is an algorithm to find this optimal ordering when the effects of executing a disjunct must be undone before another one can be tried. The algorithm is shown to have time complexity O(n log n), where n is the number of disjuncts. This is the same complexity as for the original problem where undo times are ignored.