05325nam 2200673Ia 450 991083086400332120230124183445.01-282-68408-697866126840810-470-61182-00-470-61038-7(CKB)2550000000002151(EBL)477681(OCoLC)520990483(SSID)ssj0000354063(PQKBManifestationID)11245273(PQKBTitleCode)TC0000354063(PQKBWorkID)10302232(PQKB)11736115(MiAaPQ)EBC477681(MiAaPQ)EBC4434314(EXLCZ)99255000000000215120090421d2009 uy 0engur|n|---|||||txtccrConstraint networks[electronic resource] techniques and algorithms /Christophe LecoutreLondon ISTE ;Hoboken, NJ John Wiley & Sons20091 online resource (588 p.)ISTE ;v.143Description based upon print version of record.1-84821-106-6 Includes bibliographical references and index.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 nogoods1.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. Acyclicity2.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 consistenciesChapter 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 GAC3rm4.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 diagrams5.3.3. Compressed tablesA 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.ISTEConstraint programming (Computer science)Computer algorithmsComputer networksConstraint programming (Computer science)Computer algorithms.Computer networks.004.6005.116Lecoutre Christophe1680915MiAaPQMiAaPQMiAaPQBOOK9910830864003321Constraint networks4049970UNINA