Many problems in artificial intelligence involve searching for a set of decisions that eventually lead to some desired state, or goal. The only concern, for the purposes of this dissertation, is to find a solution as fast as possible, that is, any solution is as good as any other. If the problem is structured as a tree and solutions are only found at terminal (leaf) nodes, the optimal protocol will eliminate leaf nodes as fast as possible searching the most promising leaves first. A heuristic, or rule of thumb, usually decides which nodes are more likely to lead to a goal.

Unfortunately, if the distribution of heuristic values is not uniform or if it is dense (as it is in the case where they are real-valued), existing heuristic search techniques perform badly. The best-first family of algorithms may get trapped among many competing lines of decisions and take too long to eliminate leaves, which may prove fatal if the heuristic makes mistakes. Limited discrepancy search LDS, and its current variations, developed on the intuition that heuristics make mistakes, explore leaves in order of increasing number of deviations from the heuristic path. However, it may sometimes be better to explore paths with two or more deviations that are close to the heuristic choice than to explore paths with one clear deviation. In this case, LDS fails to explore leaves in the best order.

We present an optimal algorithm WDS and a general methodology to obtain optimal protocols. We prove that WDS with an optimal cutoff policy is better than LDS and other backtracking alternatives. In formalizing WDS, we present a principled way to obtain optimal policies that minimize the expected cost to solution. We also show that the approach is general enough to obtain optimal policies in cases where there are arbitrary cost functions associated with node expansions.