LSVF: LEAST SUGGESTED VALUE FIRST: A New Search Heuristic to Reduce the Amount of Backtracking Calls in CSP

摘要

Along the years, many researches in the Artificial Intelligence (AI) field seek for new algorithms to reduce drastically the amount of memory and time consumed for general searches in the family of constraint satisfaction problems. Normally, these improvements are reached with the use of some heuristics which either prune useless tree search branches or even "indicate" the path to reach the solution (many times, the optimal solution) more easily. Many heuristics were proposed in the literature, like Static/Dynamic Highest Degree heuristic (SHD/DHD), Most Constraint Variable (MCV), Least Constraining Value (LCV), and while some can be used at the pre-processing time, others just at running time. In this paper we propose a new pre-processing search heuristic to reduce the amount of backtracking calls, namely the Least Suggested Value First (LSVF). LSVF emerges as a practical solution whenever the LCV can not distinguish how much a value is constrained. We present a pedagogical example to introduce the heuristics, realized through the general Constraint Logic Programming CHR~v, as well as the preliminary results.