共查询到20条相似文献,搜索用时 15 毫秒
1.
David Cohen Peter Jeavons Christopher Jefferson Karen E. Petrie Barbara M. Smith 《Constraints》2006,11(2-3):115-137
We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the
literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions
of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure
complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related
hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we
discuss the practical implications of these different notions of symmetry. 相似文献
2.
搜索控制问题是大多数人工智能问题求解面临的一个根本间题,而约束满足是解决这一问题的常用方法之一它源于机器视觉领域中的情景标识任务,如今在人工智能的众多领域(如规划、调度、时序推理)中获得了广泛的应用,受到了人工智能界的高度重视.在近几期的UCAI和AAAI等国际人工智能会议上这方面的内容均占有一定的比重,《A币ficial In-telligence》杂志曾于1992年出了一期约束满足问题的专辑 相似文献
3.
约束满足问题(Constraint Satisfaction Problems CSP)是人工智能的一个研究领域,诸如空间查找、规划等问题都可转化为约束满足问题。方位关系是空间关系的重要组成部分,用以确定空间对象间的一种顺序。本文研究了空间方位关系模型,给出了方位关系约束的一般表示形式。在此基础上,利用组合表推理给出了方位关系约束满足问题的一个推理求解算法,该算法的时间复杂度为O(n^2)。 相似文献
4.
提出了在二元约束满足问题中以搜索结点个数为衡量标准的求解开销模型,该模型被应用于随机二元约束满足问题的求解开销相变分析中,并且比较了模型所导出的理论开销和实际中的搜索结点个数、约束检查次数、求解时间3种衡量标准的开销之间的相似性.在模型的基础上,探讨了求解启发式减少求解开销的作用,给出了一个新的变量选择启发式. 相似文献
5.
Constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are commonly used.
While variable symmetry breaking constraints can be expressed easily and propagated efficiently using lexicographic ordering,
value symmetry breaking constraints are often difficult to formulate. In this paper, we propose two methods of using symmetry
breaking constraints to tackle value symmetries. First, we show theoretically when value symmetries in one CSP correspond to variable symmetries in another CSP of the same problem. We also show when variable symmetry breaking constraints in the two CSPs, combined using channeling constraints, are consistent. Such results
allow us to tackle value symmetries efficiently using additional CSP variables and channeling constraints. Second, we introduce
value precedence, a notion which can be used to break a common class of value symmetries, namely symmetries of indistinguishable values. While value precedence can be expressed using inefficient if-then constraints in existing CSP solvers, we propose efficient
propagation algorithms for implementing global value precedence constraints. We also characterize several theoretical properties
of the value precedence constraints. Extensive experiments are conducted to verify the feasibility and efficiency of the two
proposals. 相似文献
6.
Web Services合成是Web Services技术的重要方面,能够按要求提供选择新的服务。本文首先提出了Web Services服务约束的分类描述,进而分析了Web Services服务合成中如何按照服务约束指导服务选择,进而选择合适的服务集来满足客户的要求。该方法把动态Web Services合成转化为约束满足问题。 相似文献
7.
The Constraint Satisfaction Problem (CSP) is ubiquitous in artificialintelligence. It has a wide applicability, ranging from machine visionand temporal reasoning to planning and logic programming. This paperattempts a systematic and coherent review of the foundations ofthe techniques for constraint satisfaction. It discusses in detail thefundamental principles and approaches. This includes an initialdefinition of the constraint satisfaction problem, a graphical meansof problem representation, conventional tree search solutiontechniques, and pre-processing algorithms which are designed to makesubsequent tree search significantly easier. 相似文献
8.
弧一致性算法在二元约束满足问题中取得了成功的应用,但并不能被有效泛化至预处理非二元约束满足问题(NCSP).本文提出了处理NCSP的关联约束非二元弧一致性算法.通过随机NCSP生成器产生问题实例,分别采用关联约束非二元弧一致性算法和非二元弧一致性算法进行预处理,并对预处理后的问题实例应用回溯算法进行求解.对比分析采用两种预处理算法和不采用预处理下回溯算法的求解性能,仿真实验结果表明关联约束非二元弧一致性算法可以有效地剔除冗余的约束元组和变量域值,使关联约束非二元弧一致性回溯算法具有更良好的鲁棒性. 相似文献
9.
约束可满足性问题是一大类常出现于现实应用中的复杂问题,因其繁多的约束条件而出名。本文针对一个经典的约束可满足性问题——斑马属谁问题.基于演化算法的框架进行求解。我们采用矩阵的表示方式.并设计了相应的杂交和变异算予。实验表明.演化算法能高效地解决该问题。 相似文献
10.
11.
Conventional techniques for the constraint satisfaction problem (CSP)have had considerable success in their applications. However,there are many areas in which the performance of the basic approachesmay be improved. These include heuristic ordering of certain tasksperformed by the CSP solver, hybrids which combine compatible solutiontechniques and graph based methods which exploit the structure of theconstraint graph representation of a CSP. Also, conventionalconstraint satisfaction techniques only address problems with hardconstraints (i.e. each of which are completely satisfied or completelyviolated, and all of which must be satisfied by a validsolution). Many real applications require a more flexible approachwhich relaxes somewhat these rigid requirements. To address theseissues various approaches have been developed. This paper attempts asystematic review of them. 相似文献
12.
Luis A. Pineda 《Computer Graphics Forum》1992,11(3):333-344
In this paper we discuss two kinds of constraint satisfaction problems that arise in the context of geometric modelling, In particular in the modification of 2-D wire-frame diagrams that are subject to an arbitrary number of geometrical and topological constraints. We argue that problems in this domain can be classified in two categories that we shall call problems of reference and problems of synthesis. Since Sutherland's Sketchpad program [16], a large number of systems have addressed constraint satisfaction in terms of the representation of constraints sets as equation systems, which in turn are solved by numerical methods like local propagation, relaxation and Gaussian elimination. Here, we present an alternative framework. We argue that conceptualising constraint satisfaction as symbolic rather than “numerical” problems helps to clarify the notion of “constraint”, simplify solution methods, and to explain the intuitive inferential processes underlying the modification of drawings in the course of interactive drafting sessions. The theory presented in this paper has been tested with an experimental computer program called Graflog [5, 8, 9, 10, 11, 12]. The program has been implemented during the last four years, and has evolved through several stages. The current version is implemented in terms of two Unix-processes connected by Unix-pipes. The first is a “C” program running X windows, and handles the external aspects of the interaction. The second is a Prolog program supporting the representational structures and interpreters of the system. 相似文献
13.
14.
提出了一种基于约束满足的启发式搜索方法,用于寻找时序数据相似变化区域。该算法利用所给出的一个局部约束条件和3个全局约束条件,从整体上模仿人对相似时序数据的模糊判断过程,以此找出数据序列中相似的变化区域。并给出了该处地太阳黑子和证券交易Composiete指数数据的实验测试结果。 相似文献
15.
We describe an ant algorithm for solving constraint problems (Solnon 2002, IEEE Transactions on Evolutionary Computation 6(4): 347–357). We devise a number of variants and carry out experiments. Our preliminary results suggest that the best way
to deposit pheromone and the best heuristics for state transitions may differ from current practice 相似文献
16.
量词约束满足问题是人工智能和自动推理领域的一个重要问题.寻找多项式时间易解子类,是研究此类问题计算复杂性的关键.通过分析二元量词约束满足问题中的约束关系特征,以及量词前缀中的全称量词排列的顺序,提出了针对全称量词变量子结构的易解性质的分析方法.通过该方法,扩展了已知的基于Broken-Triangle Property的多项式时间易解子类,提出了一个更一般化的量词约束满足问题的混合易解子类.讨论了易解子类在问题结构分析中的一个应用,即通过易解子类确定量词约束满足问题的隐蔽变量集合,并通过实验分析不同易解子类所确定的集合大小.实验改造了基于回溯算法的求解器,在回溯过程中加入了易解子类的识别算法,并采用随机约束满足问题的生成模型作为测试基准.通过对比实验,验证了提出的多项式时间易解子类可以识别出更小的隐蔽变量集合,因此,新提出的易解子类在确定隐蔽变量集合方面更具优势.最后阐述了其他已有的混合易解子类也可以通过类似方法进行扩展,从而得到更多的一般化的理论结果. 相似文献
17.
Constraint Satisfaction Methods for Applications in Engineering 总被引:1,自引:0,他引:1
18.
提出一种基于约求满足的自适应神经网络方法求解车间作业调度问题。在该算法中,神经网络在运行过程中能够根据问题的约束类型、约束满足情况、启发式规则的选择来自适应调节神经元之间的连接权值,从而求得问题的可行解。仿真实验证明了算法的有效性。 相似文献
19.
Helmut Simonis 《Constraints》2007,12(1):63-92
In this paper we give an overview of some industrial applications built using global constraints. We look at three systems
from different application domains and show the core models used to express their constraints. We also consider different
search strategies that have been applied and discuss some of the application aspects. 相似文献
20.
Carla P. Gomes Bart Selman Nuno Crato Henry Kautz 《Journal of Automated Reasoning》2000,24(1-2):67-100
We study the runtime distributions of backtrack procedures for propositional satisfiability and constraint satisfaction. Such procedures often exhibit a large variability in performance. Our study reveals some intriguing properties of such distributions: They are often characterized by very long tails or heavy tails. We will show that these distributions are best characterized by a general class of distributions that can have infinite moments (i.e., an infinite mean, variance, etc.). Such nonstandard distributions have recently been observed in areas as diverse as economics, statistical physics, and geophysics. They are closely related to fractal phenomena, whose study was introduced by Mandelbrot. We also show how random restarts can effectively eliminate heavy-tailed behavior. Furthermore, for harder problem instances, we observe long tails on the left-hand side of the distribution, which is indicative of a non-negligible fraction of relatively short, successful runs. A rapid restart strategy eliminates heavy-tailed behavior and takes advantage of short runs, significantly reducing expected solution time. We demonstrate speedups of up to two orders of magnitude on SAT and CSP encodings of hard problems in planning, scheduling, and circuit synthesis. 相似文献