弧相容算法性能比较

为了化简约束满足问题的规模、有效地处理大规模难解问题,从求解算法的角度研究弧相容技术。分析讨论了8种弧相容算法各自的优势和特点。在“明月”约束求解平台上针对随机约束满足问题,对该系列弧相容算法的性能进行了测试。实验结果表明,无论是在搜索之前还是搜索过程中,AC-2001(AC-3.1)都比其他算法表现出更优异的性能。     

Knapsacks约束的弧相容改进算法

通过修改背包约束弧相容算法的数据结构,将点阵图改为有向图,解决了原背包约束弧相容算法中存在冗余计算和无效操作的问题,加快了算法对问题的求解效率.对比实验结果表明:在面对同一类问题时,因为数据结构更复杂,改进算法的初始化时间虽增加,但求解时间提高了20%~50%;在面对求解难度较高的问题时,改进算法能更好地缩减求解问题的时间.     

一种笛卡尔积压缩的负表约束上表缩减算法

利用笛卡尔积压缩方法可有效减小负表约束规模的原理, 提出一种在压缩负表上维持广义弧相容的高效算法STRC-N, 以解决负表约束维持弧相容过程中遍历所有元组导致效率低的问题. 实验结果表明, 当压缩负表上压缩率较大时, 得益于表规模的减小, 新算法相对于主流的负表约束处理算法效率更高, 性能更好, 从而实现了对负表约束处理算法的改进.     

基于AC与LmaxRPC的自适应约束传播求解算法

在现有自适应约束求解方法基础上,提出一种新的自适应约束传播求解算法ADAPTAC-LmaxRPC.该算法能根据约束的不同特性,在传播能力强但开销高的LmaxRPC与传播能力弱却开销低的AC之间自适应地切换进行约束传播.多个Benchmark实例类上的测试实验数据表明,ADAPTAC-LmaxRPC算法有效地平衡了求解效率和算法开销之间的矛盾,大幅度提高了约束求解的效率.     

变量约束网的建模和推理算法

设计的变量约束网是一个能够综合表达变量间各种约束关系的网络结构。文章中首先介绍了它的结构特征;然后给出了它的建模方法和可在Ｗｉｎｄｏｗｓ下操作的图形建模工具;最后讨论了该约束网的推理算法,即如何通过约束传播完成相关变量的求解,此算法与网络的复杂程度无关。利用文章提出的方法可构造任意复杂的变量约束网,完成对复杂系统的变量求解;与传统的表示方法相比,简化了问题求解过程,从而提高了求解效率。     

基于变量传播的弧一致性算法

在AC-3算法的基础上,提出了采用面向变量的约束传播机制新的弧一致性算法（IAC3）,算法（IAC3）引入了一个小型的附加数据结构,使得新算法的时间复杂度降低了一个幂次为O（ed2）.以小的空间代价换取了显著时间效率.新算法对于通用弧一致性算法的改进效果是明显的,是对现有弧一致性算法的提高和完善,使其实用性更好,应用前景更宽.     

参数化设计的研究与应用

参数化设计是目前CAD发展的主流方向，本文通过对各种参数设计方法分析的基础上，提出一个基于几何约束图的参数化设计模型，并给出参数化模型的数据结构和约束求解算法，此算法可以有效地检查系统的过约束和欠约束情况。     

一类参数曲线的积累平均弧长参数化方法

通过用指定方法及约束准则进行局部插值, 为高效求解采用从局部传递到整体的思想, 给出积累平均弧长参数化法的一般框架, 并在该框架下给出3种具体的积累平均弧长参数化法及相应的数值算法. 积累平均弧长参数化法的目标是降低传统方法求得的曲线关于光顺性的目标函数值, 并使方法具有可根据设计者需求生成满足条件曲线的灵活性. 实例验算表明: 在同一约束准则下, 该方法求得的全局插值曲线的目标函数值小于弦长参数化和向心参数化所对应的目标函数值.     

基于D-tree分解的欠约束与完备约束的几何约束求解

提出了解决欠约束、完备约束的几何约束问题的D-tree分解算法.首先,提出了一种适用范围更广的处理特殊约束策略,可以将这种特殊约束与普通约束统一化,采用转化策略将欠约束的几何约束问题转化为完备约束的几何约束问题.然后,根据几何约束图中结点的度的性质给出了D-tree分解算法,相比经典算法,D-tree分解算法拥有更低算法复杂度和相同的求解域.最后,根据D-tree分解算法结果的规律性,给出了一个为基于数值的求解方法导出求解序列的策略.D-tree分解算法通过导出的求解序列将提高几何约束求解中基于数值的求解方法的求解效率.     

基于权值加密的隐私安全分布式约束满足问题求解

隐私安全的分布式约束满足问题(distributed constraint satisfaction problem,DisCSP)求解算法可以很好地满足信息敏感的分布式组合求解问题的需要,为了获得更好的求解效率,提出了一种基于权值加密的隐私安全DisCSP的求解算法,对DisCSP问题中的约束基于不同的隐私权值进行加密求解;不需要增加额外的agent进行隐私约束的一致性检查,实现分布式的安全求解策略;对于可能出现的推理信息,用随机选择策略来避免信息泄漏.试验表明,该算法可以减少信息的传递量和计算的复杂性,因而具有更好的求解效率.     

约束问题求解的一个统一方法

给出了一个新的求解约束的方法──动态约束算法．它通过引入新的约束类型，使变量操作和约束操作算法统一起来．在新的求解约束过程中，不需再区分变量与约束．     

一个并发约束程序设计语言的定义与实现

设计实现了并发约束程序设计语言COPS.该语言结合约束对象、不确定性计算及约束储仓技术,采用基于并发约束模型的推理控制和基于优先度的规则选择策略,将说明性的知识表示、系统化和启发式的推理搜索能力以及合理的确定性计算开销统一起来.系统在电路建模、专家决策等领域的初步应用表明了该语言对构造基于约束的知识系统的适用性.COPS的出现为复杂智能问题的解决提供了可能性.     

理想约束的基本类型

许多一般力学文献中，对理想约束基本类型的阐述不够完整，有的甚至不够准确。本文给出了粗糙接触面约束的概念，并将约束分为内约束和外约束，在此基础上完整准确地阐述了理想约束的基本类型问题。     

基于变量混合调整的机械产品智能优化策略

为解决机械产品原始设计方案的可行化,提出了基于变量混合调整的优化策略,采用了基于启发式思想生成的变量因果关系图与几何约束混合求解的变量调整策略．该策略能很好地适应产品设计的各个阶段,具有良好的柔性;同时它又是约束驱动,具有很强的自适应性和灵活性．就汽车驾驶室内布置设计对该策略进行了有效的验证．     

基于约束映射关系的二维几何约束模型

在系统实现的基础上 ,提出一种依据设计过程确定约束依赖关系的参数化设计模型 ,建立约束和图元之间的映射模式 ,优化确定节点之间的更新从动性 ,从而降低约束求解的复杂度 .用户添加的约束和系统自动识别的约束能动态添加到有向约束图中 ,并支持任意图形块的选择重复 .实践证明 ,该模型算法简单 ,交互性好 ,能很好理解用户的设计意图 .     

球体约束的规范表达

研究球体的规范表达。提出平面冗余、平凡线性冗余、半线性冗余三条新的规范原则,并给出了球体约束元组的规范算法。     

协同设计动约束求解策略

将协同思想应用到产品开发过程中,由多功能小组共同参与,对设计任务进行有效的任务关联和分解,分析产品的信息流确定子任务之间的关系,通过约束网络图描述各子设计任务间的联系,为了对耦合关系的设计任务进行有效求解,提出了一种基于动约束的约束求解策略,并对协同设计过程中的约束进行有效的管理。     

约束条件在理论力学问题解决中的应用

在理论力学问题的分析、解答过程中，理解、利用各种约束，特别是一些不易引起注意的运动约束，对寻找思路和解决问题有重大作用。除加强基本概念和基本规律的训练，建立和正确理解质点、刚体等模型之外，有必要强调约束条件的寻找和利用。     

基于自由度分析几何约束求解方法中过约束和欠约束的处理

在自由度分析方法的基础上使用依赖图, 解决了约束求解过程中的过约束和欠约束的处理问题. 依赖图中保留了求解问题中变量间的依赖信息. 当系统发现矛盾的过约束时或欠约束时会给使用者显示提示信息, 由用户进行处理.