基于离散Lagrange方法的分布式SAT问题求解

基于对离散Lagrange方法(DLM)的扩充，提出一个分布式SAT求解算法：EDLMSAT。求解过程中，单个Agent的行为由预先定义的EDLM规则所决定，这些局部的行为聚集起来，形成整个系统对问题的求解趋势。设计了一些对3-SAT基准问题的模拟实验，实验结果表明了这个算法良好的求解性能。     

MU(1)内公式改名的多项式可判定性

研究判定合取范式公式F和H之间是否存在一个改名φ使得φ(F)＝H的计算复杂性。公式的改名是将命题变元映到变元本身或变无的否定的一个映射，对于极小不可满足公式的子类射MU／(1)中的公式，我们证明了其改名判定问题在多项式时间内是可判定的。     

不可满足公式的完备证明系统

合取范式(CNF)公式H到F的同态是一个从H的文字集合到F的文字集合的映射、并保持补运算和子句映到子句。同态映射保持一个公式的不可满足性。一个公式是极小不可满足的是指公式不可满足而且从中删去任一个子句后得到的公式可满足。MU(1)是子句数与变元数的差等于1的极小不可满足公式类。S．Szeider证明了：每个不可满足公式F是MU(1)中某个公式日的同态像。从而，基于MU(1)的同态证明系统与树消解证明系统是p-等价的。MU(1)中的公式可以用基础矩阵表示，本文用基础矩阵的方法证了同态证明系统ПMU（1）的完备性。     

CSP逻辑编程中一种约束评价的动态控制方法

在一些约束满足问题（ＣＳＰ）中，使需要进行的约束评价的数目减到最低限度是一个十分重要的问题。本文提出了一种改进的回溯算法，它借助基于假设的正确性维护系统ＡＴＭＳ达到了上述目的。     

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

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

一个从k-CNF到t-CNF归约的有效算法

根据极小不可满足公式的特征,对于固定的3 ≤t＜k.我们给出了一个将k-CNF公式归约到t-CNF公式的有效算法.对于给定的k-CNF公式F,t-CNF公式的转换可以在公式F的长度的线性时间内完成.     

非确定有限自动机的最短D1-同步字求解

研究了非确定有限自动机的最短D1-同步字的计算问题.针对这种自动机定义了D1W问题及其参数化版本问题p-D1W和最优问题shortest-p-D1W,证明了p-D1W和shortest-p-D1W分别属于para-NP和para-DP.利用均匀分布模型随机生成大量的非确定的有限自动机进行实验,结果表明:在定长的参数下几...     

协同任务规划中基于约束满足的资源冲突检测与消解

资源的有限性以及活动的并发执行导致协同任务中极易发生资源冲突,需施加时间约束以限定活动执行时间从而避免冲突的出现。在分析多机协同任务的基础上,将任务过程转化为带有多容量资源的任务调度模型,根据模型时间特性给出资源冲突定义及其判断准则。提出基于最小冲突集的资源冲突检测算法,其中利用时间交叠关系的特点,将资源冲突的检测与消解问题转化为连通图中闭团的检查与消除问题。进而从约束满足的角度研究了基于最小承诺策略的消解算法。实验结果表明方法的有效性。     

具有一对零同态的Morita Context环(Ⅰ)

设（A,B,V,W,ψ,）是一个Morita Context,且ψ与均为零同态,C=是相应的Morita Context环.用经典环论方法,得到了C与A,B之间的一些性质关系,同时推广了形式三角矩阵环的一些结果.     

大规模Job Shop调度的多级邻域变量排序算法

在基于约束满足的Job Shop调度问题求解过程中,变量赋值顺序是影响搜索效率的关键因素.根据问题的约束拓扑关系,提出了变量的多级邻域结构模型,在此基础上构造了一种新的变量排序算法,通过引导当前搜索介入临界区域来提高计算效率.数值实验表明该算法能够有效地改善大规模Job Shop调度问题的求解效率.