PostHeaderIcon Limited Discrepancy Search

Limited Discrepancy Search (LDS) Algorithm

Limited Discrepancy Search (LDS) is a completely general tree-search algorithm, but is most useful in the context of constraint satisfaction problems in which the entire tree is too large to search exhaustively. In that case, we would like to search that subset of the tree that is most likely to yield a solution in the time available. Assume that we can heuristically order a binary tree so that at any node, the left branch is more likely to lead to a solution than the right branch. LDS then proceeds in a series of depth-first iterations. The first iteration explores just the left-most path in the tree. The second iteration explores those root-to-leaf paths with exactly one right branch, or discrepancy in them. In general, each iteration explores those paths with exactly k discrepancies, with k ranging from zero to the depth of the tree. The last iteration explores just the right most branch. Under certain assumptions, one can show that LDS is likely to find a solution sooner than a strict left-to-right depth-first search.

Related Articles

Two-Player Games Search Algorithms

Intelligent Backtracking