Tsang Foundations of Constraint Satisfaction

Computation in Cognitive Science
1. Auflage 2014
ISBN: 978-1-4832-2049-9
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 440 Seiten, Web PDF

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.

Autoren/Hrsg.

Tsang, Edward

Inhaltsverzeichnis

1;Front Cover;1
2;Foundations of Constraint Satisfaction;4
3;Copyright Page;5
4;Table of Contents;12
5;Series Preface;6
6;Dedication;7
7;Preface;8
8;Acknowledgements;10
9;Notations and abbreviations;18
10;Chapter 1. Introduction;20
10.1;1.1 What is a constraint satisfaction problem?;20
10.2;1.2 Formal Definition of the CSP;24
10.3;1.3 Constraint Representation and Binary CSPs;29
10.4;1.4 Graph-related Concepts;31
10.5;1.5 Examples and Applications of CSPs;36
10.6;1.6 Constraint Programming;46
10.7;1.7 Structure Of Subsequent Chapters;47
10.8;1.8 Bibliographical Remarks;48
11;Chapter 2. CSP solving — An overview;50
11.1;2.1 Introduction;50
11.2;2.2 Problem Reduction;51
11.3;2.3 Searching For Solution Tuples;54
11.4;2.4 Solution Synthesis;63
11.5;2.5 Characteristics of Individual CSPs;65
11.6;2.6 Summary;70
11.7;2.7 Bibliographical Remarks;71
12;Chapter 3. Fundamental concepts in the CSP;72
12.1;3.1 Introduction;72
12.2;3.2 Concepts Concerning Satisfiability and Consistency;73
12.3;3.3 Relating Consistency to Satisfiability;83
12.4;3.4 (i,j)-consistency;87
12.5;3.5 Redundancy of Constraints;88
12.6;3.6 More Graph-related Concepts;89
12.7;3.7 Discussion and Summary;95
12.8;3.8 Bibliographical Remarks;95
13;Chapter 4. Problem reduction;98
13.1;4.1 Introduction;98
13.2;4.2 Node and Arc-consistency Achieving Algorithms;99
13.3;4.3 Path-consistency Achievement Algorithms;109
13.4;4.4 Post-conditions of PC Algorithms;120
13.5;4.5 Algorithm for Achieving k-consistency;121
13.6;4.6 Adaptive-consistency;124
13.7;4.7 Parallel/Distributed Consistency Achievement;129
13.8;4.8 Summary;134
13.9;4.9 Bibliographical Remarks;136
14;Chapter 5. Basic search strategies for solving CSPs;138
14.1;5.1 Introduction;138
14.2;5.2 General Search Strategies;139
14.3;5.3 Lookahead Strategies;143
14.4;5.4 Gather-information-while-searching Strategies;155
14.5;5.5 Hybrid Algorithms and Truth Maintenance;170
14.6;5.6 Comparison of Algorithms;171
14.7;5.7 Summary;174
14.8;5.8 Bibliographical Remarks;174
15;Chapter 6. Search orders in CSPs;176
15.1;6.1 Introduction;176
15.2;6.2 Ordering of Variables in Searching;176
15.3;6.3 Ordering of Values in Searching;203
15.4;6.4 Ordering of Inferences in Searching;206
15.5;6.5 Summary;206
15.6;6.6 Bibliographical Remarks;207
16;Chapter 7. Exploitation of problem-specific features;208
16.1;7.1 Introduction;208
16.2;7.2 Problem Decomposition;209
16.3;7.3 Recognition and Searching in k-trees;211
16.4;7.4 Problem Reduction by Removing Redundant Constraints;219
16.5;7.5 Cycle-cutsets, Stable Sets and Pseudo_Tree_Search;220
16.6;7.6 The Tree-clustering Method;231
16.7;7.7 j-width and Backtrack-bounded Search;254
16.8;7.8 CSPs with Binary Numerical Constraints;259
16.9;7.9 Summary;264
16.10;7.10 Bibliographical Remarks;269
17;Chapter 8. Stochastic search methods for CSPs;272
17.1;8.1 Introduction;272
17.2;8.2 Hill-climbing;273
17.3;8.3 Connectionist Approach;280
17.4;8.4 Summary;287
17.5;8.5 Bibliographical Remarks;288
18;Chapter 9. Solution synthesis;290
18.1;9.1 Introduction;290
18.2;9.2 Freuder's Solution Synthesis Algorithm;291
18.3;9.3 Seidel's Invasion Algorithm;299
18.4;9.4 The Essex Solution Synthesis Algorithms;306
18.5;9.5 When to Synthesize Solutions;313
18.6;9.6 Concluding Remarks;316
18.7;9.7 Bibliographical Remarks;317
19;Chapter 10. Optimization in CSPs;318
19.1;10.1 Introduction;318
19.2;10.2 The Constraint Satisfaction Optimization Problem;318
19.3;10.3 The Partial Constraint Satisfaction Problem;333
19.4;10.4 Summary;337
19.5;10.5 Bibliographical Remarks;338
20;Programs;340
21;Bibliography;402
22;Index;424