检索结果-内蒙古大学图书馆

STR3: A path-optimal filtering algorithm for table constraints

ARTIFICIAL INTELLIGENCE 2015年 220卷 1-27页

作者： Lecoutre, Christophe Likitvivatanavong, Chavalit Yap, Roland H. C. Univ Artois CRIL CNRS UMR 8188 F-62307 Lens France Natl Univ Singapore Sch Comp Singapore 117417 Singapore

Constraint propagation is a key to the success of Constraint Programming (CP). The principle is that filtering algorithms associated with constraints are executed in sequence until quiescence is reached. Many such algorithms have been proposed over the years to enforce the property called Generalized Arc Consistency (GAC) on many types of constraints, including table constraints that are defined extensionally. Recent advances in GAC algorithms for extensional constraints rely on directly manipulating tables during search. This is the case with a simple approach called Simple Tabular Reduction (STR), which systematically maintains tables of constraints to their relevant lists of tuples. In particular, STR2, a refined STR variant is among the most efficient GAC algorithms for positive table constraints. In this paper, we revisit this approach by proposing a new GAC algorithm called STR3 that is specifically designed to enforce GAC during backtrack search. By indexing tables and reasoning from deleted values, we show that STR3 can avoid systematically iterating over the full set of current tuples, contrary to STR2. An important property of STR3 is that it can completely avoid unnecessary traversal of tables, making it optimal along any path of the search tree. We also study a variant of STR3, based on an optimal circular way for traversing tables, and discuss the relationship of STR3 with two other optimal GAC algorithms introduced in the literature, namely, GAC4 and AC5TC-Tr. Finally, we demonstrate experimentally how STR3 is competitive with the state-of-the-art. In particular, our extensive experiments show that STR3 is generally faster than STR2 when the average size of tables is not reduced too drastically during search, making STR3 complementary to STR2. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Constraint satisfaction problems Generalized arc consistency non-binary constraints Backtracking search

来源：评论

学校读者我要写书评

暂无评论

Domain filtering consistencies for non-binary constraints

引用

ARTIFICIAL INTELLIGENCE 2008年第6-7期172卷 800-822页

作者： Bessiere, Christian Stergiou, Kostas Walsh, Toby CNRS U LIRMM Montpellier France Univ New S Wales Natl ICT Australia & Sch Comp Sci & Engn Kensington NSW 2033 Australia

In non-binary constraint satisfaction problems, the study of local consistencies that only prune values from domains has so far been largely limited to generalized arc consistency or weaker local consistency properties. This is in contrast with binary constraints where numerous such domain filtering consistencies have been proposed. In this paper we present a detailed theoretical, algorithmic and empirical study of domain filtering consistencies for non-binary problems. We study three domain filtering consistencies that are inspired by corresponding variable based domain filtering consistencies for binary problems. These consistencies are stronger than generalized arc consistency, but weaker than pairwise consistency, which is a strong consistency that removes tuples from constraint relations. Among other theoretical results, and contrary to expectations, we prove that these new consistencies do not reduce to the variable based definitions of their counterparts on binary constraints. We propose a number of algorithms to achieve the three consistencies. One of these algorithms has a time complexity comparable to that for generalized arc consistency despite performing more pruning. Experiments demonstrate that our new consistencies are promising as they can be more efficient than generalized arc consistency on certain non-binary problems. (c) 2007 Elsevier B.V. All rights reserved.

关键词： constraint programming constraint satisfaction problems non-binary constraints local consistency inverse consistency pairwise consistency

来源：评论

学校读者我要写书评

暂无评论

A non-binary constraint ordering heuristic for constraint satisfaction problems

引用

APPLIED MATHEMATICS AND COMPUTATION 2008年第1期198卷 280-295页

作者： Salido, Miguel A. Tech Univ Dept Informat Syst & Computat Valencia Spain

Nowadays many real problems can be modelled as constraint satisfaction problems (CSPs). A search algorithm for constraint programming requires an order in which variables and values should to be considered. Choosing the right order of variables and values can noticeably improve the efficiency of constraint satisfaction. Furthermore, the order in which constraints are studied can improve efficiency, particularly in problems with non-binary constraints. In this paper, we present a preprocess heuristic called constraint ordering heuristic (COH) that studies the constrainedness of the scheduling problem and mainly classifies the constraints so that the tightest ones are studied first. Thus, constrainedness can be known in advance and overall inconsistencies can be found earlier and the number of constraint checks can significantly be reduced. (C) 2007 Elsevier Inc. All rights reserved.

关键词： heuristic search constraint ordering non-binary constraints constrainedness

来源：评论

学校读者我要写书评

暂无评论

Partition search for non-binary constraint satisfaction

引用

INFORMATION SCIENCES 2007年第18期177卷 3639-3678页

作者： Ullmann, Julian R. Kings Coll London Dept Comp Sci London WC2R 2LS England

Previous algorithms for unrestricted constraint satisfaction use reduction search, which inferentially removes values from domains in order to prune the backtrack search tree. This paper introduces partition search, which uses an efficient join mechanism instead of removing values from domains. Analytical prediction of quantitative performance of partition search appears to be intractable and evaluation therefore has to be by experimental comparison with reduction search algorithms that represent the state of the art. Instead of working only with available reduction search algorithms, this paper introduces enhancements such as semijoin reduction preprocessing using Bloom filtering. (C) 2007 Elsevier Inc. All rights reserved.

关键词： constraint satisfaction non-binary constraints hash join multijoin decision diagram BDD consistency forward checking semijoin reduction dual search partition search random problems

来源：评论

学校读者我要写书评

暂无评论

binary vs. non-binary constraints

引用

ARTIFICIAL INTELLIGENCE 2002年第1-2期140卷 1-37页

作者： Bacchus, F Chen, XG van Beek, P Walsh, T Univ Waterloo Dept Comp Sci Waterloo ON N2L 3G1 Canada Univ Toronto Dept Comp Sci Toronto ON Canada Univ Alberta Dept Comp Sci Edmonton AB T6G 2M7 Canada Univ York Dept Comp Sci York YO1 5DD N Yorkshire England

There are two well known transformations from non-binary constraints to binary constraints applicable to constraint satisfaction problems (CSPs) with finite domains: the dual transformation and the hidden (variable) transformation. We perform a detailed formal comparison of these two transformations. Our comparison focuses on two backtracking algorithms that maintain a local consistency property at each node in their search tree: the forward checking and maintaining arc consistency algorithms. We first compare local consistency techniques such as arc consistency in terms of their inferential power when they are applied to the original (non-binary) formulation and to each of its binary transformations. For example, we prove that enforcing arc consistency on the original formulation is equivalent to enforcing it on the hidden transformation. We then extend these results to the two backtracking algorithms. We are able to give either a theoretical bound on how much one formulation is better than another, or examples that show such a bound does not exist. For example, we prove that the performance of the forward checking algorithm applied to the hidden transformation of a problem is within a polynomial bound of the performance of the same algorithm applied to the dual transformation of the problem. Our results can be used to help decide if applying one of these transformations to all (or part) of a constraint satisfaction model would be beneficial. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： non-binary constraints constraint satisfaction dual encoding hidden variable encoding

来源：评论

学校读者我要写书评

暂无评论

An optimal coarse-grained arc consistency algorithm

引用

ARTIFICIAL INTELLIGENCE 2005年第2期165卷 165-185页

作者： Bessière, C Régin, JC Yap, RHC Zhang, YL Natl Univ Singapore Sch Comp Singapore 117548 Singapore CNRS LIRMM UMR 5506 F-34392 Montpellier France ILOG F-06560 Valbonne France Texas Tech Univ Dept Comp Sci Lubbock TX 79409 USA

The use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algorithms for general constraints: fine-grained algorithms where the removal of a value for a variable will be propagated to the corresponding values for other variables, and coarse-grained algorithms where the removal of a value will be propagated to the related variables. One big advantage of coarse-grained algorithms, like AC-3, over fine-grained algorithms, like AC-4, is the ease of integration when implementing an algorithm in a constraint solver. However, fine-grained algorithms usually have optimal worst case time complexity while coarse-grained algorithms do not. For example, AC-3 is an algorithm with non-optimal worst case complexity although it is simple, efficient in practice, and widely used. In this paper we propose a coarse-grained algorithm, AC2001/3.1, that is worst case optimal and preserves as much as possible the ease of its integration into a solver (no heavy data structure to be maintained during search). Experimental results show that AC2001/3.1 is competitive with the best fine-grained algorithms such as AC-6. The idea behind the new algorithm can immediately be applied to obtain a path consistency algorithm that has the best-known time and space complexity. The same idea is then extended to non-binary constraints. (c) 2005 Elsevier B.V. All rights reserved.

关键词： arc consistency constraint programming systems constraint networks path consistency non-binary constraints

来源：评论

学校读者我要写书评

暂无评论

On forward checking for non-binary constraint satisfaction

引用

ARTIFICIAL INTELLIGENCE 2002年第1-2期141卷 205-224页

作者： Bessière, C Meseguer, P Freuder, EC Larrosa, J LIRMM CNRS F-34392 Montpellier France CSIC IIIA Bellaterra 08193 Spain Natl Univ Ireland Univ Coll Cork Cork Constraint Computat Ctr Cork Ireland UPC Dep LSI Barcelona 08034 Spain

Solving non-binary constraint satisfaction problems, a crucial challenge today, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary search algorithms to solve directly the original problem. The latter option raises some issues when we want to extend definitions written for the binary case. This paper focuses on the well-known forward checking algorithm, and shows that it can be generalized to several non-binary versions, all fitting its binary definition. The classical non-binary version, proposed by Van Hentenryck, is only one of these generalizations. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： constraint satisfaction non-binary constraints forward checking

来源：评论

学校读者我要写书评

暂无评论

From binary temporal relations to non-binary ones and back

引用

ARTIFICIAL INTELLIGENCE 2001年第1-2期128卷 1-29页

作者： Staab, S Univ Karlsruhe Inst Appl Informat & Formal Descript Methods AIFB D-76227 Karlsruhe Germany

In this paper a new approach towards temporal reasoning is presented that scales up from the temporal relations commonly used in Alien's qualitative interval calculus and in quantitative temporal constraint satisfaction problems to include interval relations with distances, temporal rules and other non-binary relations into the reasoning scheme. For this purpose, we generalize well-known methods for constraint propagation, determination of consistency and computation of the minimal network from simpler schemes that only allow for binary relations, Thereby, we find that levels of granularity play a major role for applying these techniques in our more expressive framework. Indeed, the technical preliminaries we provide are especially apt to investigate the switching between different granularities of representation, hence illucitating and exploiting the tradeoff between expressiveness and efficiency of temporal reasoning schemes on the one side and between expressiveness and understandability on the other side. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： temporal reasoning granularity non-binary constraints abstraction

来源：评论

学校读者我要写书评

暂无评论

non binary CSPs and heuristics for modeling and diagnosing dynamic systems 6th

引用

6th Congress of the Italian-Association-for-Artificial-Intelligence (AI*IA)

作者： Panati, A Univ Turin Dipartimento Informat I-10149 Turin Italy

ISBN: (纸本)3540673504

In this paper we concentrate on practical aspects of qualitative modeling and reasoning about physical systems, reporting our experience within the VMBD project(1) in applying Constraint Programming techniques to the task of diagnosing a real-life automotive subsystem. We propose a layered modeling approach: qualitative deviations equations as a high level model description language, and Constraint Satisfaction Problems (CSPs) with non binary constraints as underlying implementation formalism. An implementation of qualitative equations systems based on non binary constraints is presented, discussing the applicability of various heuristics. In particular, a greedy heuristic algorithm for cycle cutset decomposition and variable ordering is proposed for efficient reasoning on CSPs derived from qualitative equations. A prototype implementation of a constraint-based diagnostic engine has been developed using CLP(FD) and C++, and some preliminary results on the proposed modeling approach and heuristics axe reported.

关键词： qualitative modeling diagnosis constraint programming heuristics non-binary constraints

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：