.png){kind=icon}
返回
A GENERIC ARC-CONSISTENCY ALGORITHM AND ITS SPECIALIZATIONS
.png){kind=icon}
OA
AI
DOI：10.1016/0004-3702(92)90020-X.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Consistency techniques have been studied extensively in the past as a way of tackling constraint satisfaction problems (CSP). In particular, various arc-consistency algorithms have been proposed, originating from Waltz's filtering algorithm [271 and culminating in the optimal algorithm AC-4 of Mohr and Henderson [16]. AC-4 runs in O(ed2) in the worst case, where e is the number of arcs (or constraints) and d is the size of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints. In this paper, we,present a new generic arc-consistency algorithm AC-5. This algorithm is parametrized on two specified procedures and can be instantiated to reduce to AC-3 and AC-4. More important, AC-5 can be instantiated to produce an O(ed) algorithm for a number of important classes of constraints: functional, anti-functional. monotonic, and their generalization to (functional, anti-functional, and monotonic) piecewise constraints. We also show that AC-5 has an important application in constraint logic programming over finite domains [241. The kernel of the constraint solver for such a programming language is an arc-consistency algorithm for a set of basic constraints. We prove that AC-5, in conjunction with node consistency, provides a decision procedure for these constraints running in time O(ed).
Keyword:
CONSTRAINT SATISFACTION PROBLEMS
COMBINATORIAL PROBLEMS
COMPLEXITY
NETWORKS
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.9
论文数:
6.2K
被引数:
1.9W
机构
暂无机构信息
引用论文
Lung Cancer Signatures in Plasma Based on Proteome Profiling of Mouse Tumor Models.png)
Cancer CellOAAI
Cancer CellIF0
OAAI分享收藏
查看更多内容