Look-ahead value ordering for constraint satisfaction problems
Daniel Frost, Rina Dechter · 1995
Looking ahead during search is often useful when solving constraint satisfaction problems. Previous studies have shown that looking ahead helps by causing dead-ends to occur earlier in the search, and by providing information that is useful for dynamic variable ordering. In this paper, we show that another benefit of looking ahead is a useful domain value ordering heuristic, which we call look-ahead value ordering or LVO. LVO counts the number of times each value of the current variable conflicts with some value of a future variable, and the value with the lowest number of conflicts is chosen first. Our experiments show that look-ahead value ordering can be of substantial benefit, especially on hard constraint satisfaction problems. 1 Introduction In this paper we present a new heuristic for prioritizing the selection of values when searching for the solution of a constraint satisfaction problem. Because the task of finding a solution for a constraint satisfaction problem is NP-comp...