Description |
1 online resource (240 pages) |
Series |
ISTE |
|
ISTE
|
Contents |
Blank Page; Title Page; Contents; Preface; Introduction; Chapter 1. Foundations of CSP; 1.1. Basic concepts DEFINITION; 1.2. CSP framework; 1.2.1. Formalism; 1.2.2. Areas of application; 1.2.3. Extensions; 1.3. Bibliography; Chapter 2. Consistency Reinforcement Techniques; 2.1. Basic notions; 2.1.1. Equivalence; 2.1.2. K-consistency; 2.2. Arc consistency reinforcement algorithms; 2.2.1. AC-1; 2.2.2. AC-2; 2.2.3. AC-3; 2.2.4. AC-4; 2.2.5. AC-5; 2.2.6. AC-6; 2.2.7. AC-7; 2.2.8. AC2000; 2.2.9. AC2001; 2.3. Bibliography; Chapter 3. CSP Solving Algorithms; 3.1. Complete resolution methods |
|
3.1.1. The backtracking algorithm3.1.2. Look-back algorithms; 3.1.3. Look-ahead algorithms; 3.2. Experimental validation; 3.2.1. Random generation of problems; 3.2.2. Phase transition; 3.3. Bibliography; Chapter 4. Search Heuristics; 4.1. Organization of the search space; 4.1.1. Parallel approaches; 4.1.2. Distributed approaches; 4.1.3. Collaborative approaches; 4.2. Ordering heuristics; 4.2.1. Illustrative example; 4.2.2. Variable ordering; 4.2.3. Value ordering; 4.2.4. Constraints-based ordering; 4.3. Bibliography; Chapter 5. Learning Techniques; 5.1. The "nogood" concept |
|
5.1.1. Example of union and projection5.1.2. Use of nogoods; 5.1.3. Nogood handling; 5.2. Nogood-recording algorithm; 5.3. The nogood-recording-forward-checking algorithm; 5.4. The weak-commitment-nogood-recording algorithm; 5.5. Bibliography; Chapter 6. Maximal Constraint Satisfaction Problems; 6.1. Branch and bound algorithm; 6.2. Partial Forward-Checking algorithm; 6.3. Weak-commitment search; 6.4. GENET method; 6.5. Distributed simulated annealing; 6.6. Distributed and guided genetic algorithm; 6.6.1. Basic principles; 6.6.2. The multi-agent model; 6.6.3. Genetic process |
|
6.6.4. Extensions6.7. Bibliography; Chapter 7. Constraint Satisfaction and Optimization Problems; 7.1. Formalism; 7.2. Resolution methods; 7.2.1. Branch-and-bound algorithm; 7.2.2. Tunneling algorithm; 7.3. Bibliography; Chapter 8. Distributed Constraint Satisfaction Problems; 8.1. DisCSP framework; 8.1.1. Formalism; 8.1.2. Distribution modes; 8.1.3. Communication models; 8.1.4. Convergence properties; 8.2. Distributed consistency reinforcement; 8.2.1. The DisAC-4 algorithm; 8.2.2. The DisAC-6 algorithm; 8.2.3. The DisAC-9 algorithm; 8.2.4. The DRAC algorithm; 8.3. Distributed resolution |
|
8.3.1. Asynchronous backtracking algorithm8.3.2. Asynchronous weak-commitment search; 8.3.3. Asynchronous aggregation search; 8.3.4. Approaches based on canonical distribution; 8.3.5. DOC approach; 8.3.6. Generalization of DisCSP algorithms to several variables; 8.4. Bibliography; Index; Blank Page |
Summary |
Owing to their omnipresence in academia, industry, and even real life, constraint satisfaction problems (CSP) have become a subject of intense research in both artificial intelligence and operations research. This book introduces readers to the classic CSP, detailing several extensions/improvements of both formalisms and techniques for tackling a wide variety of problems. Consistency as well as flexible, dynamic, distributed, and learning aspects are thoroughly examined and illustrated with straightforward examples. This is an excellent guide for engineers and a valuable reference for research |
Bibliography |
Includes bibliographical references and index |
Notes |
Print version record |
Subject |
Computational complexity.
|
|
Constraints (Artificial intelligence)
|
|
MATHEMATICS -- Infinity.
|
|
MATHEMATICS -- Logic.
|
|
Computational complexity
|
|
Constraints (Artificial intelligence)
|
Form |
Electronic book
|
ISBN |
9781118575017 |
|
1118575016 |
|
9781118574577 |
|
1118574575 |
|
9781299186613 |
|
1299186610 |
|