Foundations of Constraint Satisfaction

PrefaceAcknowledgementsTable of contentsNotations and abbreviationsChapter 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 RemarksChapter 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 RemarksChapter 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 RemarksChapter 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 RemarksChapter 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.