3.7.135. Limited discrepancy search

A constraint for simulating limited discrepancy searchΒ [GinsbergHarvey95]. Limited discrepancy search is useful for problems for which there is a successor ordering heuristics that usually leads directly to a solution. It consists of systematically searching all paths that differ from the heuristic path in at most a very small number of discrepancies. FigureΒ 3.7.37 illustrates the successive search steps (B), (C), (D), (E) and (F) on the search tree depicted by partΒ (A). We successively explore the subtree of (A) corresponding to a discrepancy of 0, 1, 2, 3 and 4. The number on each leave indicates the total number of discrepancies to reach a leave.

Figure 3.7.37. Illustration of limited discrepancy search