Constraint Satisfaction Problems

Constraint Satisfaction Problems
CSP Formalisms and Techniques
Khaled Ghédira
Table of Contents
Preface ix
Introduction xi
Chapter 1. Foundations of CSP 1
1.1. Basic concepts . 1
1.2. CSP framework 3
1.2.1. Formalism . 4
1.2.2. Areas of application . 6
1.2.3. Extensions . 17
1.3. Bibliography 22
Chapter 2. Consistency Reinforcement Techniques 29
2.1. Basic notions 29
2.1.1. Equivalence 29
2.1.2. K-consistency . 30
2.2. Arc consistency reinforcement algorithms 32
2.2.1. AC-1 . 33
2.2.2. AC-2 . 36
2.2.3. AC-3 . 38
2.2.4. AC-4 . 41
2.2.5. AC-5 . 44
2.2.6. AC-6 . 50
2.2.7. AC-7 . 54
2.2.8. AC2000 . 61vi Constraint Satisfaction Problems
2.2.9. AC2001 . 65
2.3. Bibliography 69
Chapter 3. CSP Solving Algorithms 73
3.1. Complete resolution methods 73
3.1.1. The backtracking algorithm . 74
3.1.2. Look-back algorithms . 76
3.1.3. Look-ahead algorithms 86
3.2. Experimental validation 92
3.2.1. Random generation of problems 92
3.2.2. Phase transition . 94
3.3. Bibliography 96
Chapter 4. Search Heuristics . 99
4.1. Organization of the search space 99
4.1.1. Parallel approaches . 99
4.1.2. Distributed approaches 100
4.1.3. Collaborative approaches . 102
4.2. Ordering heuristics . 102
4.2.1. Illustrative example 102
4.2.2. Variable ordering 109
4.2.3. Value ordering 115
4.2.4. Constraints-based ordering . 116
4.3. Bibliography 117
Chapter 5. Learning Techniques 121
5.1. The “nogood” concept 122
5.1.1. Example of union and projection 123
5.1.2. Use of nogoods 125
5.1.3. Nogood handling . 125
5.2. Nogood-recording algorithm . 126
5.3. The nogood-recording-forward-checking algorithm . 129
5.4. The weak-commitment-nogood-recording algorithm . 132
5.5. Bibliography 133Table of Contents vii
Chapter 6. Maximal Constraint Satisfaction Problems . 135
6.1. Branch and bound algorithm . 136
6.2. Partial Forward-Checking algorithm . 138
6.3. Weak-commitment search . 142
6.4. GENET method 144
6.5. Distributed simulated annealing 146
6.6. Distributed and guided genetic algorithm 147
6.6.1. Basic principles 148
6.6.2. The multi-agent model . 150
6.6.3. Genetic process 152
6.6.4. Extensions . 158
6.7. Bibliography 162
Chapter 7. Constraint Satisfaction and Optimization
Problems . 165
7.1. Formalism 166
7.2. Resolution methods . 166
7.2.1. Branch-and-bound algorithm 167
7.2.2. Tunneling algorithm 170
7.3. Bibliography 178
Chapter 8. Distributed Constraint Satisfaction
Problems . 181
8.1. DisCSP framework 183
8.1.1. Formalism . 183
8.1.2. Distribution modes . 185
8.1.3. Communication models 191
8.1.4. Convergence properties 193
8.2. Distributed consistency reinforcement 195
8.2.1. The DisAC-4 algorithm 196
8.2.2. The DisAC-6 algorithm 197
8.2.3. The DisAC-9 algorithm 198
8.2.4. The DRAC algorithm 199
8.3. Distributed resolution 200
8.3.1. Asynchronous backtracking algorithm 201
8.3.2. Asynchronous weak-commitment search 204viii Constraint Satisfaction Problems
8.3.3. Asynchronous aggregation search . 205
8.3.4. Approaches based on canonical distribution 207
8.3.5. DOC approach 208
8.3.6. Generalization of DisCSP algorithms to several
variables . 214
8.4. Bibliography 215
Index 221
كلمة سر فك الضغط : books-world.net
The Unzip Password : books-world.net