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 条
  • [1] Solution Techniques for Constraint Satisfaction Problems: Foundations
    I. Miguel
    Q. Shen
    Artificial Intelligence Review, 2001, 15 : 243 - 267
  • [2] Solution Techniques for Constraint Satisfaction Problems: Advanced Approaches
    I. Miguel
    Q. Shen
    Artificial Intelligence Review, 2001, 15 : 269 - 293
  • [3] Solution techniques for constraint satisfaction problems: Advanced approaches
    Miguel, I
    Shen, Q
    ARTIFICIAL INTELLIGENCE REVIEW, 2001, 15 (04) : 269 - 293
  • [4] Introduction:: Special issue on constraint satisfaction techniques for planning and scheduling problems
    Salido, Miguel A.
    Garrido, Antonio
    Bartak, Roman
    ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2008, 21 (05) : 679 - 682
  • [5] Distance constraint satisfaction problems
    Bodirsky, Manuel
    Dalmau, Victor
    Martin, Barnaby
    Mottet, Antoine
    Pinsker, Michael
    INFORMATION AND COMPUTATION, 2016, 247 : 87 - 105
  • [6] Full constraint satisfaction problems
    Feder, Tomas
    Hell, Pavol
    SIAM JOURNAL ON COMPUTING, 2006, 36 (01) : 230 - 246
  • [7] GLOPTLAB: a configurable framework for the rigorous global solution of quadratic constraint satisfaction problems
    Domes, Ferenc
    OPTIMIZATION METHODS & SOFTWARE, 2009, 24 (4-5) : 727 - 747
  • [8] Symmetry Definitions for Constraint Satisfaction Problems
    David Cohen
    Peter Jeavons
    Christopher Jefferson
    Karen E. Petrie
    Barbara M. Smith
    Constraints, 2006, 11 : 115 - 137
  • [9] Testing Assignments to Constraint Satisfaction Problems
    Chen, Hubie
    Valeriote, Matt
    Yoshida, Yuichi
    2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, : 525 - 534
  • [10] On Classifying Continuous Constraint Satisfaction problems
    Miltzow, Tillmann
    Schmiermann, Reinier F.
    2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021), 2022, : 781 - 791
12345