Constraint Satisfaction Problems : CSP Formalisms and Techniques.
Başlık:
Constraint Satisfaction Problems : CSP Formalisms and Techniques.
Yazar:
Ghedira, Khaled.
ISBN:
9781118575017
Yazar Ek Girişi:
Basım Bilgisi:
1st ed.
Fiziksel Tanımlama:
1 online resource (159 pages)
Seri:
FOCUS
İçerik:
Title Page -- Contents -- Preface -- Introduction -- Chapter 1. Foundations of CSP -- 1.1. Basic concepts DEFINITION -- 1.2. CSP framework -- 1.2.1. Formalism -- 1.2.2. Areas of application -- 1.2.3. Extensions -- 1.3. Bibliography -- Chapter 2. Consistency Reinforcement Techniques -- 2.1. Basic notions -- 2.1.1. Equivalence -- 2.1.2. K-consistency -- 2.2. Arc consistency reinforcement algorithms -- 2.2.1. AC-1 -- 2.2.2. AC-2 -- 2.2.3. AC-3 -- 2.2.4. AC-4 -- 2.2.5. AC-5 -- 2.2.6. AC-6 -- 2.2.7. AC-7 -- 2.2.8. AC2000 -- 2.2.9. AC2001 -- 2.3. Bibliography -- Chapter 3. CSP Solving Algorithms -- 3.1. Complete resolution methods -- 3.1.1. The backtracking algorithm -- 3.1.2. Look-back algorithms -- 3.1.3. Look-ahead algorithms -- 3.2. Experimental validation -- 3.2.1. Random generation of problems -- 3.2.2. Phase transition -- 3.3. Bibliography -- Chapter 4. Search Heuristics -- 4.1. Organization of the search space -- 4.1.1. Parallel approaches -- 4.1.2. Distributed approaches -- 4.1.3. Collaborative approaches -- 4.2. Ordering heuristics -- 4.2.1. Illustrative example -- 4.2.2. Variable ordering -- 4.2.3. Value ordering -- 4.2.4. Constraints-based ordering -- 4.3. Bibliography -- Chapter 5. Learning Techniques -- 5.1. The "nogood" concept -- 5.1.1. Example of union and projection -- 5.1.2. Use of nogoods -- 5.1.3. Nogood handling -- 5.2. Nogood-recording algorithm -- 5.3. The nogood-recording-forward-checking algorithm -- 5.4. The weak-commitment-nogood-recording algorithm -- 5.5. Bibliography -- Chapter 6. Maximal Constraint Satisfaction Problems -- 6.1. Branch and bound algorithm -- 6.2. Partial Forward-Checking algorithm -- 6.3. Weak-commitment search -- 6.4. GENET method -- 6.5. Distributed simulated annealing -- 6.6. Distributed and guided genetic algorithm -- 6.6.1. Basic principles -- 6.6.2. The multi-agent model -- 6.6.3. Genetic process.
6.6.4. Extensions -- 6.7. Bibliography -- Chapter 7. Constraint Satisfaction and Optimization Problems -- 7.1. Formalism -- 7.2. Resolution methods -- 7.2.1. Branch-and-bound algorithm -- 7.2.2. Tunneling algorithm -- 7.3. Bibliography -- Chapter 8. Distributed Constraint Satisfaction Problems -- 8.1. DisCSP framework -- 8.1.1. Formalism -- 8.1.2. Distribution modes -- 8.1.3. Communication models -- 8.1.4. Convergence properties -- 8.2. Distributed consistency reinforcement -- 8.2.1. The DisAC-4 algorithm -- 8.2.2. The DisAC-6 algorithm -- 8.2.3. The DisAC-9 algorithm -- 8.2.4. The DRAC algorithm -- 8.3. Distributed resolution -- 8.3.1. Asynchronous backtracking algorithm -- 8.3.2. Asynchronous weak-commitment search -- 8.3.3. Asynchronous aggregation search -- 8.3.4. Approaches based on canonical distribution -- 8.3.5. DOC approach -- 8.3.6. Generalization of DisCSP algorithms to several variables -- 8.4. Bibliography -- Index -- Blank Page -- Blank Page.
Özet:
A Constraint Satisfaction Problem (CSP) consists of a set of variables, a domain of values for each variable and a set of constraints. The objective is to assign a value for each variable such that all constraints are satisfied. CSPs continue to receive increased attention because of both their high complexity and their omnipresence in academic, industrial and even real-life problems. This is why they are the subject of intense research in both artificial intelligence and operations research. This book introduces the classic CSP and details several extensions/improvements of both formalisms and techniques in order to tackle a large variety of problems. Consistency, flexible, dynamic, distributed and learning aspects are discussed and illustrated using simple examples such as the n-queen problem. Contents 1. Foundations of CSP. 2. Consistency Reinforcement Techniques. 3. CSP Solving Algorithms. 4. Search Heuristics. 5. Learning Techniques. 6. Maximal Constraint Satisfaction Problems. 7. Constraint Satisfaction and Optimization Problems. 8. Distibuted Constraint Satisfaction Problems. About the Authors Khaled Ghedira is the general managing director of the Tunis Science City in Tunisia, Professor at the University of Tunis, as well as the founding president of the Tunisian Association of Artificial Intelligence and the founding director of the SOIE research laboratory. His research areas include MAS, CSP, transport and production logistics, metaheuristics and security in M/E-government. He has led several national and international research projects, supervised 30 PhD theses and more than 50 Master's theses, co-authored about 300 journal, conference and book research papers, written two text books on metaheuristics and production logistics and co-authored three others.
Notlar:
Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2017. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.
Tür:
Elektronik Erişim:
Click to View