最坏情况下#3-SAT问题最小上界

最坏情况下#SAT问题上界的研究已成为一个热门的研究领域.#SAT问题的时间复杂性是根据问题实例的大小所组成的函数计算所得.#SAT问题实例的大小不仅依赖于变量的数量,还依赖于子句的数量.以子句数量为参数研究#SAT问题在最坏情况下的上界,不仅可以从另一个角度衡量算法的好坏,而且在某种程度上更能准确地反映出算法的性能.首先从子句数量的角度证明了之前提出的基于扩展规则的模型计数算法(CER算法)的上界O(2m),其中m是公式中子句的数量.为了提高#3-SAT问题的求解效率,采用了多种分裂规则,进一步给出了一种基于Davis-Putnam-Logemann-Loveland(DPLL)的#3-SAT算法MCDP.通过分析该算法得到了以子句数量为参数的#3-SAT问题在最坏情况下的上界O(1.8393m).     

一种基于扩展规则的#SAT 求解系统

#SAT 问题是SAT 问题的扩展,需要计算出给定命题公式集合的模型个数.通过将问题求解沿着归结的反方向进行,并利用容斥原理解决由此带来的空间复杂性问题,提出了一种基于扩展规则的模型计数和加权模型计数问题求解框架,可以看作是目前所有模型计数问题求解方法的一种补方法.证明了该方法的完备性和有效性,设计了基于扩展规则的#SAT 求解系统:JLU-ERWMC.实验结果表明,JLU-ERWMC 在有些问题中优于目前最为高效的#SAT 问题求解系统.     

图规划框架下的启发式搜索的研究与发展

随着智能规划研究的深入,以往的规划器已不能满足实际应用的需要.为了提高规划器求解实际问题的能力,启发式搜索产生了.对近10年来各种启发式搜索方法进行了分析,指出了它们的优缺点,并进行了比较.同时对智能规划及其启发式搜索的未来发展方向进行了分析与预测,旨在让研究和关心该领域的学者较为全面地了解这一领域.     

最坏情况下X3SAT最大海明距离问题最小上界

X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离。提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支。给出了多种化简规则,这些规则很好地提高了算法的时间效率。证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的O(1.7107n)缩小到O(1.6760n),其中n为公式中变量的数目。     

求解#SMT问题的局部搜索算法

#SMT问题是SMT问题的扩展,它需要计算一阶逻辑公式F所有可满足解的个数.目前,该问题已被广泛应用于编译器优化、硬件设计、软件验证和自动化推理等领域.随着#SMT问题的广泛应用,设计可以求解较大规模#SMT实例的求解器亟待解决.基于以上原因,设计了一种求解较大规模#SMT实例的近似求解器——VolComputeWithLocalSearch.它在现有的#SMT精确求解算法的基础上加入差分进化算法,通过调用体积计算工具qhull,进而给出#SMT问题的近似解.算法采用群体规则减少体积计算的次数,差分进化方法快速地枚举各个有解的区域.另外,从理论上证明了VolComputeWithLocalSearch求解器可以得到精确解的下界,使其可以应用在软件测试等只需要知道问题下界的领域.实验结果表明：VolComputeWithLocalSearch求解器是稳定的、具有快速的求解能力,并在高维问题上具有很好的表现.     

部分可观察强规划中约减观察变量的研究

给出了一种约减观察变量方法——假设所有的状态变量都不是观察变量,在此基础上逐步增加必要的观察变量,从而最终得到一个必要的观察变量集合.在添加必要的观察变量过程中,该方法不要求得到所有变量的相关信息,从而具有更好的通用性.根据是否存在单个观察变量能够区分域中任意两个状态的问题,分别给出了两种约减观察变量方法:当存在一个观察变量可以区分规划域中任意两个状态时,算法可以得到一个最小的观察变量集合;当不存在这样一个观察变量时,算法可以得到一个尽可能小的观察变量集合,但不能保证该集合最小.     

可能性扩展规则的推理和知识编译

在扩展规则的基础上提出了可能性扩展规则。给出了基于可能性扩展规则的可能性逻辑推理方法,利用互补因子的概念来估价推理问题的复杂度。扩展了经典逻辑的蕴含可控制类和可满足可控制类的定义,提出了可能性蕴含可控制类、不一致性程度计算可控制类的概念。在可能性扩展规则的基础上提出了EPPCCCL(each pair of possibilistic clauses contains complementary literals)理论,并证明了该理论是在最优化形式蕴含可控制类和不一致性程度计算可控制类中的,可以作为可能性     

模糊c-均值算法和万有引力算法求解模糊聚类问题

针对单纯使用模糊c-均值算法(FCM)求解模糊聚类问题的不足,首先,提出一种改进的万有引力搜索算法,通过一定概率按照不同方式对速度进行更新,有效增大了种群的搜索域.其次,提出了模糊万有引力搜索算法(FG-SA).最后,在模糊万有引力搜索算法(FGSA)和模糊c-均值算法(FCM)的基础上,提出了一种新算法(FGSAFCM)来求解模糊聚类问题,有效避免了单纯使用模糊c-均值算法时对初始值敏感且易于陷入局部最优的缺点.采用目标函数和有效性评价函数作为评价标准,选取10个经典数据集作为测试数据,实验结果表明,新算法比单一的模糊c-均值算法有更高的准确性和鲁棒性.     

基于延迟部分推理的快速前向规划系统

根据动作组件诱发关系的存在和抵制计算的必要性,提出一个计算松弛规划解的新方法——延迟部分推理.该方法在考虑动作删除效果的假定下,构造不包含任何互斥关系的组件规划图,通过定义"松弛诱发"关系预测后续规划过程中可能出现的组件诱发现象,在松弛规划解提取阶段判断动作组件间的"松弛诱发"关系并选择抵制动作避免可能发生的消极作用.基于延迟部分推理方法定义了新的启发式函数和剪枝策略,设计了规划系统FFc并在多个国际通用的测试域上进行实验.结果表明,FFc较之Fast-Forward在求解效率和求解质量方面都有显著的提高.     

人工智能问题中的相变现象研究

在人工智能研究领域的很多问题中存在着相变现象(phase transition)。问题中的某个参数发生较小的变化便会引起问题的某个属性发生突变。相变现象与问题求解结构有很大关系,将从相变现象的发展、相关概念以及相变现象与问题求解的关系等方面对相变现象做全面的论述,提出了有待解决的开放性问题,并对相变现象的研究给以总结和展望。