并行工程中时间约束网络建立及冲突检测研究

由于并行工程产品开发过程的复杂性，产品开发过程中存在着大量的时间约束关系，因时间约束关系的违反而千万的过程冲突极易发生，本文提出一种以IDEF3过程模型为基础建立并行工程产品过程的时间约束网络的方法，在将该时间约束网络转化为定量时间约束网络的基础上，提出一种面向定量时间约束网络的冲突检测的方法，基于时间约束网络的冲突检测方法能有效发现并行工程产品开发过程中的过程冲突。     

EMERGENCE FROM LOCAL EVALUATION FUNCTION

This paper presents a new look on emergence from the aspect of locality and globality of evaluation functions for solving traditional computer problems. We first translate the Constraint Satisfaction Problem (CSP) into the multi-agent system, and then show how a global solution emerges from the system in which every agent uses a local evaluation function to decide its action, while comparing to other traditional algorithms,such as Local search and Simulated Annealing which use global evaluation functions. We also give some computer experimental results on large-scale N-queen problems and k-Coloring problems, and show that emergence only depends on problem instance, not details of agent settings, i.e. in some CSPs, the system can self-organize to a global solution~ but can not in some other CSPs no matter what settings of agents have.     

加权约束满足问题的改进深度优先搜索算法

回顾了加权约束满足问题的基本概念，给出了求解的标准深度优先搜索算法，并探讨了利用变量间的约束关系，改进标准深度优先搜索算法的搜索上下界；在此基础上，给出了一种改进的深度优先分枝定界算法，该算法的一个特点是通过循环迭代求解子问题来改进上下界．针对随机约束满足问题模型生成的测试数据的数值计算结果显示，改进算法可以大大缩短求解时间。     

一种面向并行工程的产品开发过程关系模型

为了处理产品开发过程由串行到并行的转变而引起的问题，全面地表示且维持产品开发过程中各开发小组及小组成员间应满足的关系，保证开发过程满足顾客需求，本文分析了并行产品开发过程的特点，提出了一种适合这些特点的产品开发过程关系的层次表示模型，介绍了此关系模型的实现方法和它与并行工程环境中其它系统的集成关系，给出了此关系模型在产品开发过程中的应用     

作战任务和资源间的匹配模型及求解算法研究

针对作战任务和作战资源的匹配问题,提出了一种匹配模型及其求解算法.首先分析了作战任务和资源的属性,建立了匹配问题的约束满足模型.基于改进的多优先级动态列表规划算法提出了一种匹配模型的求解算法,并结合实例进行了分析验证.结果表明,算法中引入任务与资源选择优先权参数,可以有效消解优先权冲突,增加匹配的灵活性.     

基于SAT和BDD的频繁序列挖掘技术

【目的】研究模式挖掘领域中的频繁序列挖掘技术,由于序列模式挖掘存在指数级的搜索空间,且传统的SAT求解算法无法高效求解大规模数据集的缺点,因此研究符号表示和操作技术,用来避免冗余计算。【方法】提出基于SAT的频繁序列挖掘的符号OBDD算法,基于深度优先算法的思想,首先将频繁序列挖掘问题构建为SAT模型,其次对变量进行排序并将约束子句分类后分别描述为OBDD,利用OBDD的"与"操作得到满足SAT的所有频繁序列模式。【结果】实例结果表明,该方法准确可行。【结论】该方法能有效缩减搜索空间,提高求解效率。     

满足置换恒等式的强wrpp半群的性质和特征

通过引入满足置换恒等式的强wrpp半群的定义,得到了满足置换恒等式的强wrpp半群的一些性质。通过引入正规带上的最小半格同余ε,证明了当E(S)是矩形带时,满足置换恒等式的强wrpp半群是交换R-左可消幺半群与矩形带的直积。     

结合高级正向推理过程的可满足性问题解决器

提出了一个可满足性问题解决器,它结合了DPLL(Davis Putnam Loge- mann and Loveland)算法和作为高级推理技术之一的失败性文字检查(FLD,Failed Literal Detection)技术.在失败性文字检查技术中,又提出了动态筛选方法,它包含了两条规则: 内部和外部筛选.在保证能在每个决策层上发现大部分失败性文字的同时,降低了失败性文字检查所测试的文字数目及相应的计算时间.不同于其他类型的预定义的删除标准,在这一方法中文字的删除是动态的,从这点上讲,文中的失败性文字检查算法可以适应不同类型的测试基准实例.许多不必要的测试可以被避免,因而提高了失败性文字检查的计算速度.为了进一步提高失败性文字检查的效率,故此还增加了其他静态的测试约束.实验表明,经过优化后的失败性文字检查算法的效率明显高于其他的高级正向推理技术.     

关于群的一阶公式的注记

讨论群的命题的可满足性，证明了超积ПＤ Ｓｎ中有秩≥２的自由群，如果群Ｇ满足存在公式φ并且Ｇ同构于ΠＤ Ｓｎ的一个子群，则存在有限群满足ψ。     

关于SAT问题物理模型猜想的一个反例

针对关于ＳＡＴ问题物理模型的一个猜想，得到了该猜想成立的必要条件，然后构造出反例，说明该猜想是不成立的，同时指出，考虑到“算法吸引区”的存在，这并不降低应用该物理模型求解ＳＡＴ问题的良好的现实效果。