共查询到16条相似文献,搜索用时 93 毫秒
1.
2.
针对一个具有精确可满足性相变现象的大值域随机约束满足问题,提出了两种启发式动态回溯算法,即基于动态度的ddeg-MAC(dynamic degree-maintaining arc consistency)回溯算法和基于值域与动态度比值的dom/ddeg-MAC(dom/dynamic degree-maintaining arc consistency)回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量,利用维持弧相容(MAC)技术为挑选的变量进行赋值。当赋值无法进行时,再执行动态回溯修正变量的赋值。数值实验结果表明:在控制参数非常接近理论相变点时,算法仍然能够有效地找到问题的解。与经典回溯算法相比,这两种启发式动态回溯算法具有显著的优越性。 相似文献
3.
约束满足问题是人工智能领域中最基本的NP完全问题之一。多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型。其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性。为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向。 相似文献
4.
一种基于预处理技术的约束满足问题求解算法 总被引:4,自引:0,他引:4
相容性技术作为约束满足问题的一种有效求解技术,不论是在求解前的预处理过程中,还是在搜索过程中,都扮演着极为重要的角色.文中对预处理阶段的相容性技术进行改进和信息抽取,提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC*,并嵌入到BT框架中,形成新的搜索算法BT MPAC和BT MPAC*,给出了其正确性证明,通过复杂性分析得到Pre-AC和Pre-AC*的时间复杂度分别是O(nd)和O(ed2),明显低于目前最流行的弧相容技术的时间复杂度O(ed3).实验测试结果表明:对于不同类别的用例,新算法的执行效率是弧相容维护算法的2~50倍. 相似文献
5.
6.
7.
8.
9.
弧相容算法是约束满足问题的基本压缩求解空间算法之一,很多优秀的高级算法都以高性能的弧相容算法作为核心.近年来,以GPU为计算工具加速并行计算被用来尝试解决许多问题.基于GPU和基本的并行算法,提出一种适合GPU运算的约束网络表示模型N-E,给出其生成算法BuildNE.结合细粒度的弧相容算法——AC4,基于N-E模型提出AC4的并行化算法AC4\\+GPU与改进算法AC4\\+GPU+,使弧相容算法得以扩展到GPU上执行.实验结果验证了该算法的可行性,与AC4算法的比较,其在一些规模较小的问题上取得了10%~50%的加速,在一些规模较大的问题上则加速1~2个数量级.为今后进一步在GPU上以并行形式解决其他约束满足问题提供了一种核心算法方案. 相似文献
10.
约束满足问题是人工智能领域的重要研究方向,其求解方法有三种,搜索、一致性算法和约束传播,其中一致性算法通常通过缩减问题域来提高搜索算法的效率.着重介绍了几种常用的一致性算法,并对几种常用算法进行了分析、比较和研究. 相似文献
11.
非二元约束满足问题求解 总被引:12,自引:1,他引:12
在约束满足问题(CSP)的研究中,大部分工作集中在二元约束,但处理实际问题时,常常会遇到非二元约束的情况.该文在概要地讨论了两类求解非二元约束问题方法的基础上,研究了一种将约束传播技术和一般弧相容回溯算法相结合的非二元约束求解方法,并在设计开发的约束求解工具“明月SOLVER1.0”中实现了该方法,以典型例子给出了实现系统的运行结果. 相似文献
12.
Many temporal applications like planning and scheduling can be viewed as special cases of the numeric and symbolic temporal constraint satisfaction problem. Thus we have developed a temporal model, TemPro, based on the interval Algebra, to express such applications in term of qualitative and quantitative temporal constraints. TemPro extends the interval algebra relations of Allen to handle numeric information. To solve a constraint satisfaction problem, different approaches have been developed. These approaches generally use constraint propagation to simplify the original problem and backtracking to directly search for possible solutions. The constraint propagation can also be used during the backtracking to improve the performance of the search. The objective of this paper is to assess different policies for finding if a TemPro network is consistent. The main question we want to answer here is how much constraint propagation is useful for finding a single solution for a TemPro constraint graph. For this purpose, we have experimented by randomly generating large consistent networks for which either arc and/or path consistency algorithms (AC-3, AC-7 and PC-2) were applied. The main result of this study is an optimal policy combining these algorithms either at the symbolic (Allen relation propagation) or at the numerical level. 相似文献
13.
动态识别三维几何约束冲突的方法研究 总被引:5,自引:3,他引:5
吴永明 《计算机辅助设计与图形学学报》2000,12(8):618-623
基于装配几何特征的广义几何约束图,避免了传统几何约束图的超图性质和模糊性,为几何约束满足问题提供了一个清晰的分析模型。文中以此模型来分析产生约束冲突的原因。空间分析法定义和推导了约束满足空间约束满足条件,提出了自由空间和自由度的计算方法,并据此在动态满足三维几何约束的过程中识别约束冲突,明确指出产生约束冲突的原因。 相似文献
14.
15.
We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n + n′) plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n′ is the number of values in the union of their domains. It is the first efficient algorithm that achieves bound consistency for all variables, and not only the assignment variables.Partially supported by DFG grant SA 933/1-1.Partially supported by the EU IST Programme, IST-1999-14186 (ALCOM-FT). 相似文献
16.
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. 相似文献