Edward Tsang. Foundations of constraint satisfaction

Монография, London, 1996, 441 с.
Многие проблемы можно сформулировать как проблемы удовлетворения ограничений (CSP), хотя исследователи, неподготовленные в этой области, иногда не могут их распознать и, следовательно, не могут использовать специализированные методы для их решения. В последние годы удовлетворение ограничений стало рассматриваться как основная проблема во многих приложениях, например, во временных рассуждениях, распределении ресурсов, планировании. Его роль в логическом программировании также признана. Важность удовлетворения ограничений отражается в обилии публикаций, сделанных конференциях.
Разбросанность и неорганизованность материала в области удовлетворения ограничений, а также разнообразие терминологии, используемой в разных частях литературы, делают эту важную тему более сложной для изучения, чем это необходимо. Одна из целей этой книги — обобщить результаты исследований CSP на данный момент и помочь новичкам в этой области легче изучить эту проблему. Целью здесь является организация и объяснение существующей работы в области CSP, а также предоставление указаний на передовые исследования в этой области. Эта книга в основном посвящена алгоритмам решения CSP.
Этот том может использоваться в качестве справочника исследователями искусственного интеллекта или в качестве учебника для студентов продвинутых курсов по искусственному интеллекту. Это также должно помочь инженерам по знаниям применять существующие методы для решения CSP или проблем, в которые встроены CSP. Большинство алгоритмов, описанных в этой книге, объясняются в псевдокоде и иногда иллюстрируются кодами Пролога (чтобы проиллюстрировать, как можно реализовать алгоритмы). Пролог был выбран потому, что по сравнению с другими языками он позволяет более четко показать логику алгоритмов. Здесь я старался, насколько это возможно, придерживаться чистого Пролога и избегать использования нелогических конструкций, таких как утверждения и отступления.
Preface
Acknowledgements
Table of contents
Figures
Notations and abbreviations
Introduction
What is a constraint satisfaction problem?
Formal Definition of the CSP
Constraint Representation and Binary CSPs
Graph-related Concepts
Examples and Applications of CSPs
Constraint Representation and Binary CSPs
Graph-related Concepts
Examples and Applications of CSPs
Constraint Programming
Structure Of Subsequent Chapters
Bibliographical Remarks
CSP solving — An overview
Introduction
Problem Reduction
Searching For Solution Tuples
Solution Synthesis
Characteristics of Individual CSPs
Solution Synthesis
Characteristics of Individual CSPs
Solution Synthesis
Characteristics of Individual CSPs
Solution Synthesis
Characteristics of Individual CSPs
Summary
Bibliographical Remarks
Fundamental concepts in the CSP
Introduction
Concepts Concerning Satisfiability and Consistency
Relating Consistency to Satisfiability (i, j)-consistency
Redundancy of Constraints
More Graph-related Concepts Discussion and Summary Bibliographical Remarks
Problem reduction
Introduction
Node and Arc-consistency Achieving Algorithms
Path-consistency Achievement Algorithms
Post-conditions of PC Algorithms
Algorithm for Achieving k-consistency
Adaptive-consistency
Parallel/Distributed Consistency Achievement
Summary
Bibliographical Remarks
Basic search strategies for solving CSPs
Introduction
General Search Strategies
Lookahead Strategies
Gather-information-while-searching Strategies
Hybrid Algorithms and Truth Maintenance
Comparison of Algorithms
Summary
Bibliographical Remarks
Search orders in CSPs
Introduction
Ordering of Variables in Searching
Ordering of Values in Searching
Ordering of Inferences in Searching
Summary
Bibliographical Remarks
Exploitation of problem-specific features
Introduction
Problem Decomposition
Recognition and Searching in k-trees
Problem Reduction by Removing Redundant Constraints
Cycle-cutsets, Stable Sets and Pseudo Tree Search
The Tree-clustering Method
j-width and Backtrack-bounded Search
CSPs with Binary Numerical Constraints
Summary
Bibliographical Remarks
Stochastic search methods for CSPs
Introduction
Hill-climbing
Connectionist Approach
Summary
Bibliographical Remarks
Solution synthesis
Introduction
Freuder’s Solution Synthesis Algorithm
Seidel’s Invasion Algorithm
The Essex Solution Synthesis Algorithms
When to Synthesize Solutions
Concluding Remarks Bibliographical Remarks
Bibliographical Remarks
Optimization in CSPs
Introduction
The Constraint Satisfaction Optimization Problem
The Partial Constraint Satisfaction Problem
Summary
Bibliographical Remarks
Programs
Bibliography
Index