next up previous contents
Next: Solution Repair Up: Constructive Search Previous: Incomplete Constructive Search

Intelligent Backtracking and nogood Learning

ECLiPSe offers facilities for programmers to define specific constructive search algorithms. Intelligent backtracking has been implemented in ECLiPSe. However it is not offered as a library, because in practice any reduction in the amount of search due to intelligent backtracking is dominated by the cost of accessing and updating the necessary data structures.

The information about which constraints are involved, when a failure occurs during search, is useful for recording combinations of variable values which are mutually inconsistent. Such conflict sets can be used to impose extra constraints called nogoods which are learned during search.

nogood learning has also been implemeted in ECLiPSe and is proving useful on some benchmark examples, but as yet no library supporting nogoods is available. A paper describing this work [RR96] is available from the IC-Parc home page (whose URL is given in section 6 below).

Joachim Schimpf
Wed Sep 3 18:07:19 BST 1997