Paper ID: 8565
BM + BJ = BMJ
9th Conference on Artificial Intelligence for Applications
Page Numbers : 257-262
URL: This publication is available at this URL.
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