Combinatorial Search: From Algorithms to Systems

Ebook Details


Youssef Hamadi

Year 2013
Pages 139
Publisher Springer
Language en
ISBN 9783642414817
File Size 3.09 MB
File Format PDF
Download Counter 1,371

Ebook Description

Although they are believed to be unsolvable in general, tractability results suggest that some practical NP-hard problems can be efficiently solved. Combinatorial search algorithms are designed to efficiently explore the usually large solution space of these instances by reducing the search space to feasible regions and using heuristics to efficiently explore these regions. Various mathematical formalisms may be used to express and tackle combinatorial problems, among them the constraint satisfaction problem (CSP) and the propositional satisfiability problem (SAT). These algorithms, or constraint solvers, apply search space reduction through inference techniques, use activity-based heuristics to guide exploration, diversify the searches through frequent restarts, and often learn from their mistakes.