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 条
  • [41] Fine-Grained Time Complexity of Constraint Satisfaction Problems
    Jonsson, Peter
    Lagerkvist, Victor
    Roy, Biman
    [J]. ACM TRANSACTIONS ON COMPUTATION THEORY, 2021, 13 (01)
  • [42] An evolutionary constraint satisfaction solution for over the cell channel routing
    Unveren, A
    Acan, A
    [J]. INTEGRATION-THE VLSI JOURNAL, 2004, 37 (02) : 121 - 133
  • [43] Turing Machines with Atoms, Constraint Satisfaction Problems, and Descriptive Complexity
    Klin, Bartek
    Lasota, Slawomir
    Ochremiak, Joanna
    Torunczyk, Szymon
    [J]. PROCEEDINGS OF THE JOINT MEETING OF THE TWENTY-THIRD EACSL ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC (CSL) AND THE TWENTY-NINTH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2014,
  • [44] Enumeration Strategies for Solving Constraint Satisfaction Problems: A Performance Evaluation
    Soto, Ricardo
    Crawford, Broderick
    Olivares, Rodrigo
    Herrera, Rodrigo
    Johnson, Franklin
    Paredes, Fernando
    [J]. ARTIFICIAL INTELLIGENCE PERSPECTIVES AND APPLICATIONS (CSOC2015), 2015, 347 : 169 - 179
  • [45] Correlating the Community Structure of Constraint Satisfaction Problems with Search Time
    Medema, Michel
    Lazovik, Alexander
    [J]. INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS, 2022, 31 (07)
  • [46] CONSTANT-QUERY TESTABILITY OF ASSIGNMENTS TO CONSTRAINT SATISFACTION PROBLEMS
    Chen, Hubie
    Valeriote, Matt
    Yoshida, Yuichi
    [J]. SIAM JOURNAL ON COMPUTING, 2019, 48 (03) : 1022 - 1045
  • [47] Enumeration Strategies to Solve Constraint Satisfaction Problems Performance evaluation
    Soto, Ricardo
    Crawford, Broderick
    Olivares, Rodrigo
    Herrera, Rodrigo
    Johnson, Franklin
    Paredes, Fernando
    [J]. 2015 10TH IBERIAN CONFERENCE ON INFORMATION SYSTEMS AND TECHNOLOGIES (CISTI), 2015,
  • [48] Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
    Abbasi-Zadeh, Sepehr
    Bansal, Nikhil
    Guruganesh, Guru
    Nikolov, Aleksandar
    Schwartz, Roy
    Singh, Mohit
    [J]. ACM TRANSACTIONS ON ALGORITHMS, 2022, 18 (04)
  • [49] Minimal cycle cutset methods to solve constraint satisfaction problems
    Chowdhury, U
    Gupta, DK
    [J]. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1995, 57 (1-2) : 45 - 55
  • [50] Equivariant algorithms for constraint satisfaction problems over coset templates
    Lasota, Slawomir
    [J]. INFORMATION PROCESSING LETTERS, 2017, 118 : 44 - 52
12345