Constraint satisfaction problems : CSP formalisms and techniques / Khaled Ghédira.

Format:

Book

Author/Creator:

Ghédira, Khaled.

Series:

Focus series (London, England)

Computer engineering and IT series

Language:

English

Subjects (All):

Constraint programming (Computer science).

Physical Description:

1 online resource (240 p.)

Edition:

1st ed.

Place of Publication:

London : ISTE ; Hoboken, N.J. : Wiley, 2013.

Language Note:

English

Summary:

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

Contents:

Blank Page; 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 algorithm3.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 projection5.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. Extensions6.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 algorithm8.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

Notes:

Description based upon print version of record.

Includes bibliographical references and index.

Description based on metadata supplied by the publisher and other sources.

ISBN:

9781118574522

1118574524

9781118575017

1118575016

9781118574577

1118574575

9781299186613

1299186610

OCLC:

828299042