Constraint networks [[electronic resource] ] : techniques and algorithms / / Christophe Lecoutre

• Autore: Lecoutre Christophe
• Pubblicazione: London, : ISTE; Hoboken, NJ, : John Wiley & Sons, 2009
• Descrizione fisica: 1 online resource (588 p.)
• Disciplina: 004.6; 005.116
• Soggetto topico: Constraint programming (Computer science); Computer algorithms; Computer networks
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Constraint Networks; Contents; Acknowledgements; Notation; Main Acronyms; List of Algorithms; Introduction; Chapter 1. Constraint Networks; 1.1. Variables and constraints; 1.2. Networks of variables and constraints; 1.2.1. Basic definitions; 1.2.2. Associated (hyper)graphs; 1.2.3. Instantiations and solutions; 1.3. Examples of constraint networks; 1.3.1. Queens problem; 1.3.2. Crossword problem; 1.3.3. Sudoku problem; 1.3.4. Edge-matching puzzles; 1.4. Partial orders, decisions, nogoods and properties; 1.4.1. Partial orders; 1.4.2. Decisions and nogoods ; 1.4.3. Properties on values and variables1.5. Data structures to represent constraint networks; 1.5.1. Representation of finite domains; 1.5.2. Representation of constraints; Chapter 2. Random and Structured Networks; 2.1. Random constraint networks; 2.1.1. Classical models; 2.1.2. Models RB and RD; 2.1.3. Random constraint networks in intension; 2.1.4. Benchmarks; 2.1.4.1. Random series; 2.1.4.2. Random series containing a small structure; 2.2. Structured constraint networks; 2.2.1. Backbones and backdoors; 2.2.2. Cores and cliques; 2.2.3. Acyclicity ; 2.2.4. Small world structure and morphing technique2.2.5. Benchmarks; 2.2.5.1. Main series; 2.2.5.2. Other series; Part one. Inference; Chapter 3. Consistencies; 3.1. Basic consistencies; 3.2. Stability of consistencies; 3.3. Domain-filtering consistencies; 3.4. Higher-order consistencies; 3.4.1. Taking the right path; 3.4.2. Relation-based consistencies; 3.5. Global consistency; 3.5.1. Identifying global consistency; 3.5.2. Toward tractability; 3.5.2.1. Relational CSP classes; 3.5.2.2. Structural CSP classes; 3.5.2.3. Hybrid CSP classes; 3.6. Caveats about node, arc and path consistencies ; Chapter 4. Generic GAC Algorithms4.1. Coarse-grained propagation schemes; 4.1.1. Arc-oriented propagation scheme; 4.1.2. Variable-oriented propagation scheme; 4.1.3. Applying forward checking; 4.2. Iterating over valid tuples; 4.3. GAC3 and GAC2001; 4.4. More about general-purpose GAC algorithms; 4.4.1. Important properties; 4.4.1.1. Incrementality; 4.4.1.2. Multi-directionality; 4.4.1.3. Substitutability; 4.4.2. Overview; 4.5. Improving the efficiency of generic GAC algorithms; 4.5.1. Exploiting cardinality of conflict sets; 4.5.2. Exploiting residues; 4.5.2.1. Algorithm GAC3rm ; 4.5.2.2. Complexity issues4.5.2.3. Residues within MAC; 4.5.3. Exploiting bitwise operations; 4.5.3.1. Binary representation; 4.5.3.2. Algorithms AC3bit and AC3bit+rm; 4.6. Experimental results; 4.7. Discussion; Chapter 5. Generalized Arc Consistency for Table Constraints; 5.1. Classical schemes; 5.1.1. Positive table constraints; 5.1.2. GAC-valid scheme; 5.1.3. GAC-allowed scheme; 5.1.4. Illustration; 5.2. Indexing-based approaches; 5.2.1. NextIn indexing; 5.2.2. NextDiff indexing; 5.3. Compression-based approaches; 5.3.1. Tries; 5.3.2. Multi-valued decision diagrams ; 5.3.3. Compressed tables
• Sommario/riassunto: A major challenge in constraint programming is to develop efficient generic approaches to solve instances of the constraint satisfaction problem (CSP). With this aim in mind, this book provides an accessible synthesis of the author's research and work in this area, divided into four main topics: representation, inference, search, and learning. The results obtained and reproduced in this book have a wide applicability, regardless of the nature of the problem or the constraints involved, making it an extremely user-friendly resource for those involved in this field.
• Titolo autorizzato: Constraint networks
• ISBN: 1-282-68408-6; 9786612684081; 0-470-61182-0; 0-470-61038-7
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910830864003321
• Lo trovi qui: Univ. Federico II
• Serie: ISTE