INCOMPLETE DEPTH-FIRST SEARCH TECHNIQUES: A SHORT SURVEY
Roman Barták · 2004
Constraint Satisfaction Problem (CSP) is a discrete combinatorial problem and hence search algorithms belong to the main constraint satisfaction techniques. There exist local search techniques exploring complete but inconsistent assignments and depth-first search techniques extending partial consistent assignments towards complete assignments. For most problems it is impossible to explore complete search space so incomplete techniques are used. In this paper, we survey incomplete depth-first search techniques, in particular, generic incomplete search techniques and discrepancy-based search techniques.