Foundations of constraint satisfaction / / Edward Tsang

• Record Nr.: UNINA9910812507903321
• Autore: Tsang Edward
• Pubbl/distr/stampa: London, England ; ; San Diego, California : , : Academic Press Limited, , 1993; ©1993
• ISBN: 1-4832-2049-4
• Descrizione fisica: 1 online resource (440 p.)
• Collana: Computation in Cognitive Science
• Disciplina: 006.33
• Soggetti: Constraints (Artificial intelligence) - Mathematics; Constraints (Artificial intelligence) - Data processing
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Front Cover; Foundations of Constraint Satisfaction; Copyright Page; Series Preface; Dedication; Preface; Acknowledgements; Table of Contents; Notations and abbreviations; Chapter 1. Introduction; 1.1 What is a constraint satisfaction problem?; 1.2 Formal Definition of the CSP; 1.3 Constraint Representation and Binary CSPs; 1.4 Graph-related Concepts; 1.5 Examples and Applications of CSPs; 1.6 Constraint Programming; 1.7 Structure Of Subsequent Chapters; 1.8 Bibliographical Remarks; Chapter 2. CSP solving - An overview; 2.1 Introduction; 2.2 Problem Reduction; 2.3 Searching For Solution Tuples2.4 Solution Synthesis; 2.5 Characteristics of Individual CSPs; 2.6 Summary; 2.7 Bibliographical Remarks; Chapter 3. Fundamental concepts in the CSP; 3.1 Introduction; 3.2 Concepts Concerning Satisfiability and Consistency; 3.3 Relating Consistency to Satisfiability; 3.4 (i,j)-consistency; 3.5 Redundancy of Constraints; 3.6 More Graph-related Concepts; 3.7 Discussion and Summary; 3.8 Bibliographical Remarks; Chapter 4. Problem reduction; 4.1 Introduction; 4.2 Node and Arc-consistency Achieving Algorithms; 4.3 Path-consistency Achievement Algorithms; 4.4 Post-conditions of PC Algorithms4.5 Algorithm for Achieving k-consistency; 4.6 Adaptive-consistency; 4.7 Parallel/Distributed Consistency Achievement; 4.8 Summary; 4.9 Bibliographical Remarks; Chapter 5. Basic search strategies for solving CSPs; 5.1 Introduction; ; 5.2 General Search Strategies; 5.3 Lookahead Strategies; 5.4 Gather-information-while-searching Strategies; 5.5 Hybrid Algorithms and Truth Maintenance; 5.6 Comparison of Algorithms; 5.7 Summary; 5.8 Bibliographical Remarks; Chapter 6. Search orders in CSPs; 6.1 Introduction; 6.2 Ordering of Variables in Searching; 6.3 Ordering of Values in Searching6.4 Ordering of Inferences in Searching; 6.5 Summary; 6.6 Bibliographical Remarks; Chapter 7. Exploitation of problem-specific features; 7.1 Introduction; 7.2 Problem Decomposition; 7.3 Recognition and Searching in k-trees; 7.4 Problem Reduction by Removing Redundant Constraints; 7.5 Cycle-cutsets, Stable Sets and Pseudo_Tree_Search; 7.6 The Tree-clustering Method; 7.7 j-width and Backtrack-bounded Search; 7.8 CSPs with Binary Numerical Constraints; 7.9 Summary; 7.10 Bibliographical Remarks; Chapter 8. Stochastic search methods for CSPs; 8.1 Introduction; 8.2 Hill-climbing8.3 Connectionist Approach; 8.4 Summary; 8.5 Bibliographical Remarks; Chapter 9. Solution synthesis; 9.1 Introduction; 9.2 Freuder's Solution Synthesis Algorithm; 9.3 Seidel's Invasion Algorithm; 9.4 The Essex Solution Synthesis Algorithms; 9.5 When to Synthesize Solutions; 9.6 Concluding Remarks; 9.7 Bibliographical Remarks; Chapter 10. Optimization in CSPs; 10.1 Introduction; 10.2 The Constraint Satisfaction Optimization Problem; 10.3 The Partial Constraint Satisfaction Problem; 10.4 Summary; 10.5 Bibliographical Remarks; Programs; Bibliography; Index
• Sommario/riassunto: Foundations of Constraint Satisfaction