Nogood Recording for static and dynamic constraint satisfaction problems
Nogood Recording for static and dynamic constraint satisfaction problems
复制标题
静态和动态约束满足问题的Nogood Recording
DOI：
10.1109/tai.1993.633935
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
G. Verfaillie
中科院分区：
文献类型：
--
作者：
T. Schiex;G. Verfaillie
Many AI synthesis problems such as planning, scheduling or design may be encoded in a constraint satisfaction problem (CSP). A CSP is typically defined as the problem of finding any consistent labeling for a fixed set of variables satisfying all given constraints between these variables. However, for many real tasks, the set of constraints to consider may evolve because of the environment or because of user interactions. The problem considered here is the solution maintenance problem in such a dynamic CSP (DCSP). The authors propose a new class of constraint recording algorithms called Nogood Recording that may be used for solving both static and dynamic CSPs. It offers an interesting compromise, polynomially bounded in space, between an ATMS-like approach and the usual static constraint satisfaction algorithms.
