Research Catalog

Title

Foundations of constraint satisfaction / Edward Tsang.

Author

Tsang, Edward.

Publication

London ; San Diego : Academic Press, [1993], ©1993.

Items in the Library & Off-site

Holdings

Details

Description

xviii, 421 pages : illustrations; 24 cm

Subjects

• Artificial intelligence > Related to > Mind
• Constraints (Artificial intelligence)

Bibliography (note)

• Includes bibliographical references (p. [383]-403) and index.

Contents

• Ch. 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 -- Ch. 2. CSP solving - An overview. 2.2. Problem Reduction. 2.3. Searching For Solution Tuples. 2.4. Solution Synthesis. 2.5. Characteristics of Individual CSPs -- Ch. 3. Fundamental concepts in the CSP. 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 -- Ch. 4. Problem reduction. 4.2. Node and Arc-consistency Achieving Algorithms. 4.3. Path-consistency Achievement Algorithms. 4.4. Post-conditions of PC Algorithms. 4.5. Algorithm for Achieving k-consistency. 4.6. Adaptive-consistency. 4.7. Parallel/Distributed Consistency Achievement.
• Ch. 5. Basic search strategies for solving CSPs. 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 -- Ch. 6. Search orders in CSPs. 6.2. Ordering of Variables in Searching. 6.3. Ordering of Values in Searching. 6.4. Ordering of Inferences in Searching -- Ch. 7. Exploitation of problem-specific features. 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 PseudoT̲reeS̲earch. 7.6. The Tree-clustering Method. 7.7. j-width and Backtrack-bounded Search. 7.8. CSPs with Binary Numerical Constraints -- Ch. 8. Stochastic search methods for CSPs. 8.2. Hill-climbing. 8.3. Connectionist Approach -- Ch. 9. Solution synthesis. 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 -- Ch. 10. Optimization in CSPs. 10.2. The Constraint Satisfaction Optimization Problem. 10.3. The Partial Constraint Satisfaction Problem.

ISBN

0127016104

LCCN

gb 93066472

OCLC

ocm28932191

Owning Institutions

Columbia University Libraries