Stubborness: a possible enhancement for backjumping and nogood recording
Thomas Schiex, Gérard Verfaillie · European Conference on Artificial Intelligence · 1994
Abstract. The Conflict directed Backjumping (CBJ) algorithm at-tempts to reduce the number of nodes visited within the constraintsatisfaction problem by analyzing failures. The Nogood Recording(NR these analyzes as constraints in the CSP solved itself. In bo ) algorithms incorporate,during the search,part ofthe results ofth cases,failures are the basic information used to increase efficiency. It isshown how artificially augmenting the number of failures mayleadto notable improvements in efficiency. Introduction In the Constraint Satisfaction Problem (CSP) we are given a set ofvariables, where each variable has a finite domain, and a set of con-straints, where eachconstraint acts betweena subsetof the variables.The problem is then to find an assignment of values to variables,from their respective domains, such that the constraint are satisfied.Many real world problems, such as scheduling, design or planning,can be cast as CSP’s. However, the CSP framework presents somesignificant limitations when confronted with the demands ofpracti-cal applications. Among them, the combinatorial complexity of thesatisfaction problem (