MAC-DBT Revisited

摘要

Dynamic Backtracking {DBT) is a well known algorithm for solving Constraint Satisfaction Problems. In DBT, variables are allowed to keep their assignment during backjump, if they are compatible with the set of eliminating explanations. A previous study has shown that when DBT is combined with variable ordering heuristics, it performs poorly compared to standard Conflict-directed Backjumping (CBJ) [Bak94]. In later studies, DBT was enhanced with constraint propagation methods. The MAC-DBT algorithm was reported by [JDB00] to be the best performing version, improving on both standard DBT and on FC-DBT by a large factor. The present study evaluates the DBT algorithm from a number of aspects. First we show that the advantage of MAC-DBT over FC-DBT holds only for a static ordering. When dynamic ordering heuristics are used, FC-DBT outperforms MAC-DBT. Second, we show theoretically that a combined version of DBT that uses both FC and MAC performs equal or less computation at each step than MAC-DBT. An empirical result which presents the advantage of the combined version on MAC-DBT is also presented. Third, following the study of [Bak94], we present a version of MAC-DBT and FC-DBT which does not preserve assignments which were jumped over. It uses the Nogood mechanism of DBT only to determine which values should be restored to the domains of variables. These versions of MAC-DBT and FC-DBT outperform all previous versions.