UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 8565

BM + BJ = BMJ
Prosser,P.

Publication Type: Conference Proceedings
Appeared in: 9th Conference on Artificial Intelligence for Applications
Page Numbers : 257-262
Publisher: N/A
Year: 1993
ISBN/ISSN: 0-8186-3840-0

URL: This publication is available at this URL.

Abstract:

The backmarking routine (BM) attempts to minimize the execution of redundant consistency checks within the constraint satisfaction problem, whereas the backjumping routine (BJ) attempts to minimize the number of nodes visited within the search tree. By making these two algorithms explicit, it is shown that both routines can be combined to result in BMJ, an algorithm that marks and jumps back. Functions BM and BJ are described in an explicit/iterative manner, in terms of separate forward/backward moves. By doing this the author explicates the search knowledge required by these routines. He then makes this information available to both, allowing BM and BJ to be combined. Empirical evidence is presented to position BMJ with respect to chronological backtracking, backmarking, backjumping, and forward checking

Keywords: constraint satisfaction, backmarking, backjumping


Bibtex entry Endnote XML