LEADER 05358nam 2200685Ia 450 001 9910139510103321 005 20210209192744.0 010 $a1-282-68408-6 010 $a9786612684081 010 $a0-470-61182-0 010 $a0-470-61038-7 035 $a(CKB)2550000000002151 035 $a(EBL)477681 035 $a(OCoLC)520990483 035 $a(SSID)ssj0000354063 035 $a(PQKBManifestationID)11245273 035 $a(PQKBTitleCode)TC0000354063 035 $a(PQKBWorkID)10302232 035 $a(PQKB)11736115 035 $a(MiAaPQ)EBC477681 035 $a(MiAaPQ)EBC4434314 035 $a(EXLCZ)992550000000002151 100 $a20090421d2009 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aConstraint networks$b[electronic resource] $etechniques and algorithms /$fChristophe Lecoutre 210 $aLondon $cISTE ;$aHoboken, NJ $cJohn Wiley & Sons$d2009 215 $a1 online resource (588 p.) 225 1 $aISTE ;$vv.143 300 $aDescription based upon print version of record. 311 $a1-84821-106-6 320 $aIncludes bibliographical references and index. 327 $aConstraint 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 327 $a1.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 327 $a2.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 327 $aChapter 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 327 $a4.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 327 $a5.3.3. Compressed tables 330 $aA 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. 410 0$aISTE 606 $aConstraint programming (Computer science) 606 $aComputer algorithms 606 $aComputer networks 608 $aElectronic books. 615 0$aConstraint programming (Computer science) 615 0$aComputer algorithms. 615 0$aComputer networks. 676 $a004.6 676 $a005.116 700 $aLecoutre$b Christophe$0951605 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910139510103321 996 $aConstraint networks$92151321 997 $aUNINA