A Graph Based Synthesis Algorithm for Solving CSPs.
Wanlin Pang, Scott D. Goodwin · 2003
. Many AI tasks can be formalized as constraint satisfaction problems (CSPs), which involve finding values for variables subject to a set of constraints. While solving a CSP is an NP-complete task in general, it is believed that efficiency can be significantly improved by exploiting the characteristics of the problem. In this paper, we present a solution synthesis algorithm called !-CDGT which is an existing algorithm named CDGT augmented with a constraint representative graph called !-graph. We show that the worst-case complexity of the !-CDGT algorithm is better than other related algorithms. Keywords: constraint satisfaction problems 1 Introduction Constraint satisfaction problems (CSPs) involve finding values for variables subject to constraints which permit or exclude certain combinations of values. Since many problems in AI and other areas of computer science can be formulated as CSPs, it has been a research subject for a long time and researchers have approached the s...