Foundations of Constraint Satisfaction
Computation in Cognitive Science
Free Global Shipping
No minimum orderDescription
Foundations of Constraint Satisfaction discusses the foundations of constraint satisfaction and presents algorithms for solving constraint satisfaction problems (CSPs). Most of the algorithms described in this book are explained in pseudo code, and sometimes illustrated with Prolog codes (to illustrate how the algorithms could be implemented). Comprised of 10 chapters, this volume begins by defining the standard CSP and the important concepts around it and presenting examples and applications of CSPs. The reader is then introduced to the main features of CSPs and CSP solving techniques (problem reduction, searching, and solution synthesis); some of the most important concepts related to CSP solving; and problem reduction algorithms. Subsequent chapters deal with basic control strategies of searching which are relevant to CSP solving; the significance of ordering the variables, values and compatibility checking in searching; specialized search techniques which gain their efficiency by exploiting problem-specific features; and stochastic search approaches (including hill climbing and connectionist approaches) for CSP solving. The book also considers how solutions can be synthesized rather than searched for before concluding with an analysis of optimization in CSPs. This monograph can be used as a reference by artificial intelligence (AI) researchers or as a textbook by students on advanced AI courses, and should also help knowledge engineers apply existing techniques to solve CSPs or problems which embed CSPs.
Table of Contents
Preface
Acknowledgements
Table of contents
Notations and abbreviations
Chapter 1 Introduction
1.1 What is a Constraint Satisfaction Problem?
1.1.1 Example 1 —The N-Queens Problem
1.1.2 Example 2 — The Car Sequencing Problem
1.2 Formal Definition of the CSP
1.2.1 Definitions of Domain and Labels
1.2.2 Definitions of Constraints
1.2.3 Definitions of Satisfiability
1.2.4 Formal Definition of Constraint Satisfaction Problems
1.2.5 Task in a CSP
1.2.6 Remarks on the Definition of CSPs
1.3 Constraint Representation and Binary CSPs
1.4 Graph-Related Concepts
1.5 Examples and Applications of CSPs
1.5.1 The N-Queens Problem
1.5.2 The Graph Colouring Problem
1.5.3 The Scene Labelling Problem
1.5.4 Temporal Reasoning
1.5.5 Resource Allocation in AI Planning and Scheduling
1.5.6 Graph Matching
1.5.7 Other Applications
1.6 Constraint Programming
1.7 Structure Of Subsequent Chapters
1.8 Bibliographical Remarks
Chapter 2 CSP Solving — An Overview
2.1 Introduction 31
2.1.1 Soundness and Completeness of Algorithms
2.1.2 Domain Specific vs. General Methods
2.2 Problem Reduction
2.2.1 Equivalence
2.2.2 Reduction of a Problem
2.2.3 Minimal Problems
2.3 Searching For Solution Tuples
2.3.1 Simple Backtracking
2.3.2 Search Space of CSPs
2.3.3 General Characteristics of CSP's Search Space
2.3.4 Combining Problem Reduction and Search
2.3.5 Choice Points in Searching
2.3.6 Backtrack-Free Search
2.4 Solution Synthesis
2.5 Characteristics of Individual CSPs
2.5.1 Number of Solutions Required
2.5.2 Problem Size
2.5.3 Types of Variables and Constraints
2.5.4 Structure of the Constraint Graph in Binary - Constraint-Problems
2.5.5 Tightness of a Problem
2.5.6 Quality of Solutions
2.5.7 Partial Solutions
2.6 Summary 51
2.7 Bibliographical Remarks
Chapter 3 Fundamental Concepts in the CSP
3.1 Introduction
3.2 Concepts Concerning Satisfiability and Consistency
3.2.1 Definition of Satisfiability
3.2.2 Definition of k-Consistency
3.2.3 Definition of Node- and Arc-Consistency
3.2.4 Definition of Path-Consistency
3.2.5 Refinement of PC
3.2.6 Directional Arc- and Path-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.2.1 Achieving NC
4.2.2 A Naive Algorithm for Achieving AC
4.2.3 Improved AC Achievement Algorithms
4.2.4 AC-4, an Optimal Algorithm for Achieving AC
4.2.5 Achieving DAC
4.3 Path-Consistency Achievement Algorithms
4.3.1 Relations Composition
4.3.2 PC-1, a Naive PC Algorithm
4.3.3 PC-2, an Improvement Over PC-1
4.3.4 Further Improvement of PC Achievement Algorithms
4.3.5 GAC4: Problem Reduction for General CSPs
4.3.6 Achieving DPC
4.4 Post-Conditions of PC Algorithms
4.5 Algorithm for Achieving k-Consistency
4.6 Adaptive-Consistency
4.7 Parallel/Distributed Consistency Achievement
4.7.1 A connectionist Approach to AC Achievement
4.7.2 Extended Parallel Arc-Consistency
4.7.3 Intractability of Parallel Consistency
4.8 Summary
4.9 Bibliographical Remarks
Chapter 5 Basic Search Strategies for Solving CSPs
5.1 Introduction
5.2 General Search Strategies
5.2.1 Chronological Backtracking
5.2.2 Iterative Broadening
5.3 Lookahead Strategies
5.3.1 Forward Checking
5.3.2 The Directional AC-Lookahead Algorithm
5.3.3 The AC-Lookahead Algorithm
5.3.4 Remarks on Lookahead Algorithms
5.4 Gather-Information-while-Searching Strategies
5.4.1 Dependency Directed Backtracking
5.4.2 Learning Nogood Compound Labels Algorithms
5.4.3 Backchecking and Backmarking
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.2.1 The Minimal Width Ordering Heuristic
6.2.2 The Minimal Bandwidth Ordering Heuristic
6.2.3 The Fail First Principle
6.2.4 The Maximum Cardinality Ordering
6.2.5 Finding the Next Variable to Label
6.3 Ordering of Values in Searching
6.3.1 Rationale Behind Values Ordering
6.3.2 The Min-Conflict Heuristic and Informed Backtrack
6.3.3 Implementation of Informed-Backtrack
6.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.3.1 "Easy Problems": CSPs which Constraint Graphs are Trees
7.3.2 Searching in Problems which Constraint Graphs are k-Trees
7.4 Problem Reduction by Removing Redundant Constraints
7.5 Cycle-Cutsets, Stable Sets and Pseudo_Tree_Search
7.5.1 The Cycle-Cutset Method
7.5.2 Stable Sets
7.5.3 Pseudo-Tree Search
7.6 The Tree-Clustering Method
7.6.1 Generation of Dual Problems
7.6.2 Addition and Removal of Redundant Constraints
7.6.3 Overview of the Tree-Clustering Method
7.6.4 Generating Chordal Primal Graphs
7.6.5 Finding Maximum Cliques
7.6.6 Forming Join-Trees
7.6.7 The Tree-Clustering Procedure
7.7 j-Width and Backtrack-Bounded Search
7.7.1 Definition of j-Width
7.7.2 Achieving Backtrack-Bounded Search
7.8 CSPs with Binary Numerical Constraints
7.8.1 Motivation
7.8.2 The AnalyseLongestPaths Algorithm
7.9 Summary
7.10 Bibliographical Remarks
Chapter 8 Stochastic Search Methods for CSPs
8.1 Introduction
8.2 Hill-Climbing
8.2.1 General Hill-Climbing Algorithms
8.2.2 The Heuristic Repair Method
8.2.3 A Gradient-Based Conflict Minimization Hill-Climbing Heuristic
8.3 Connectionist Approach
8.3.1 Overview of Problem Solving Using Connectionist Approaches
8.3.2 GENET, a Connectionist Approach to the CSP
8.3.3 Completeness of GENET
8.3.4 Performance of GENET
8.4 Summary
8.5 Bibliographical Remarks
Chapter 9 Solution synthesis
9.1 Introduction
9.2 Freuder's Solution Synthesis Algorithm
9.2.1 Constraints Propagation in Freuder's Algorithm
9.2.2 Algorithm Synthesis
9.2.3 Example of Running Freuder's Algorithm
9.2.4 Implementation of Freuder's Synthesis Algorithm
9.3 Seidel's Invasion Algorithm
9.3.1 Definitions and Data Structure
9.3.2 The Invasion Algorithm
9.3.3 Complexity of Invasion and Minimal Bandwidth Ordering
9.3.4 Example Illustrating the Invasion Algorithm
9.3.5 Implementation of the Invasion Algorithm
9.4 The Essex Solution Synthesis Algorithms
9.4.1 The AB Algorithm
9.4.2 Implementation of AB
9.4.3 Variations of AB
9.4.4 Example of Running AB
9.4.5 Example of Running AP
9.5 When to Synthesize Solutions
9.5.1 Expected Memory Requirement of AB
9.5.2 Problems Suitable for Solution Synthesis
9.5.3 Exploitation of Advanced Hardware
9.6 Concluding Remarks
9.7 Bibliographical Remarks
Chapter 10 Optimization in CSPs
10.1 Introduction
10.2 The Constraint Satisfaction Optimization Problem
10.2.1 Definitions and Motivation
10.2.2 Techniques for Tackling the CSOP
10.2.3 Solving CSOPs with Branch and Bound
10.2.4 Tackling CSOPs Using Genetic Algorithms
10.3 The Partial Constraint Satisfaction Problem
10.3.1 Motivation and Definition of the PCSP
10.3.2 Important Classes of PCSP and Relevant Techniques
10.4 Summary
10.5 Bibliographical Remarks
Programs
Bibliography
Index
Product details
- No. of pages: 440
- Language: English
- Copyright: © Academic Press 1993
- Published: August 24, 1993
- Imprint: Academic Press
- eBook ISBN: 9781483220499
About the Author
Edward Tsang
Ratings and Reviews
There are currently no reviews for "Foundations of Constraint Satisfaction"