Solution techniques for constraint satisfaction problems: Foundations

被引：10
作者：
Miguel, I [1 ]
Shen, Q [1 ]
机构：
[1] Univ Edinburgh, Sch Artificial Intelligence, Div Informat, Edinburgh EH1 1HN, Midlothian, Scotland
来源：
ARTIFICIAL INTELLIGENCE REVIEW | 2001年 / 15卷 / 04期
基金：
英国工程与自然科学研究理事会;
关键词：
Constraint Satisfaction Problems; constraint graph; tree search; pre-processing; consistency enforcing;
D O I：
10.1023/A:1011039901653
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The Constraint Satisfaction Problem (CSP) is ubiquitous in artificial intelligence. It has a wide applicability, ranging from machine vision and temporal reasoning to planning and logic programming. This paper attempts a systematic and coherent review of the foundations of the techniques for constraint satisfaction. It discusses in detail the fundamental principles and approaches. This includes an initial definition of the constraint satisfaction problem, a graphical means of problem representation, conventional tree search solution techniques, and pre-processing algorithms which are designed to make subsequent tree search significantly easier.
引用
收藏
页码：243 / 267
页数：25
相关论文
共 50 条
  • [31] The Asymptotics of the Clustering Transition for Random Constraint Satisfaction Problems
    Budzynski, Louise
    Semerjian, Guilhem
    JOURNAL OF STATISTICAL PHYSICS, 2020, 181 (05) : 1490 - 1522
  • [32] There are no pure relational width 2 constraint satisfaction problems
    Dalmau, Victor
    INFORMATION PROCESSING LETTERS, 2009, 109 (04) : 213 - 218
  • [33] Random Subcubes as a Toy Model for Constraint Satisfaction Problems
    Thierry Mora
    Lenka Zdeborová
    Journal of Statistical Physics, 2008, 131 : 1121 - 1138
  • [34] A CHARACTERISATION OF FIRST-ORDER CONSTRAINT SATISFACTION PROBLEMS
    Larose, Benoit
    Loten, Cynthia
    Tardif, Claude
    LOGICAL METHODS IN COMPUTER SCIENCE, 2007, 3 (04)
  • [35] An Extensive Evaluation of Portfolio Approaches for Constraint Satisfaction Problems
    Amadini, Roberto
    Gabbrielli, Maurizio
    Mauro, Jacopo
    INTERNATIONAL JOURNAL OF INTERACTIVE MULTIMEDIA AND ARTIFICIAL INTELLIGENCE, 2016, 3 (07): : 81 - 86
  • [36] Comparing evolutionary algorithms on binary constraint satisfaction problems
    Craenen, BGW
    Eiben, AE
    van Hemert, JI
    IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2003, 7 (05) : 424 - 444
  • [37] Robustness, stability, recoverability, and reliability in constraint satisfaction problems
    Federico Barber
    Miguel A. Salido
    Knowledge and Information Systems, 2015, 44 : 719 - 734
  • [38] Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
    Marx, Daniel
    PODS '21: PROCEEDINGS OF THE 40TH SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, 2021, : 19 - 29
  • [39] Combining ARC consistency and informed backtracking techniques for constraint satisfaction
    Boutheina, J
    Ghedira, K
    Proceedings of the Eighth IASTED International Conference on Artificial Intelligence and Soft Computing, 2004, : 364 - 368
  • [40] Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
    Barto, Libor
    Battistelli, Diego
    Berg, Kevin M.
    38TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2021), 2021, 187
12345