Optimal satisficing tree searches
Dan Geiger, Jeffrey A. Barnett · 1991
We provide an algorithm that finds optimal search strategies for and trees and or trees. Our model includes three outcomes when a node is explored: (1) finding a solution, (2) not finding a solution and realizing that there are no solutions beneath the current node (pruning), and (3) not finding a solution but not pruning the nodes below. The expected cost of examining a node and the probabilities of the three outcomes are given. Based on this input, the algorithm generates an order that minimizes the expected search cost.