用吴方法求解可满足性问题(Ⅰ)--算法变换

本文在算法变换的思想指导下,研究了用吴方法求解可满足性问题的特点.通过建立吴方法的基本操作与子句间有限制的归结操作的对应,证明了吴方法求解可满足性问题基本上是一种以特征列计算为核心的有限制的子句归结过程,不仅使吴方法和归结法相互引入新的概念和认识,而且在算法实现时可以避免复杂的多项式计算,同时可以更好地利用问题特性和已有经验以获得更高的效率.     

可满足性求解技术研究

求解公式的可满足性在诸如形式化验证、电子设计自动化与人工智能等众多领域中都具有非常重要的理论与应用价值,成为近年来的研究热点。本文针对命题公式与一阶公式的可满足性问题,重点介绍了布尔可满足性与可满足性模理论求解技术的基本原理,并且根据算法的类型进行分类阐述,分析了各种算法的优缺点。最后,讨论了目前面临的主要挑战,对今后的研究方向进行了展望。     

求解可满足性问题的改进的模拟退火算法

该文为可满足性问题的高效近似求解提出了改进的模拟退火算法。数值实验表明,对于该文随机产生的测试问题例,改进的模拟退火算法完全胜过局部搜索算法、模拟退火算法以及目前国际上流行的WSAT算法。     

一个约束可满足性问题的演化算法求解

约束可满足性问题是一大类常出现于现实应用中的复杂问题,因其繁多的约束条件而出名。本文针对一个经典的约束可满足性问题——斑马属谁问题．基于演化算法的框架进行求解。我们采用矩阵的表示方式．并设计了相应的杂交和变异算予。实验表明．演化算法能高效地解决该问题。     

命题逻辑可满足性问题的算法分析

1 引言可满足性问题(以下简称SAT)是问:对于一个命题逻辑公式,是否存在对其变元的一个真值赋值使之成立?这个问题在许多领域都有非常重要的意义,其快速求解算法的研究成为计算机科学的中心课题之一。例如在机器定理证明领域,某命题是否是一个和谐的公理集合的推论,这个问题归结为该命题的反面与该公理集合一起是否是不可满足的。通过量词消去技术和Herbrand定理的作用,谓词逻辑公式的不可满足性可以归结为命题逻辑公式的不可满足性。在知识库维护中,当知识以逻辑公式的形式表达时,知识库的一致性检查可以归结为命题逻辑公式的可满足性。在开放逻辑中,新事实是否与已有的知识矛盾,当遇到事实反驳时如何求得最大和谐的知识集,这些问题最后都要归结为命题逻辑公式的可满足性。1971年Cook首次证明了SAT是NP-完全的,从而大量的计算问题都可以归约到SAT。正是由于SAT的重要地位,各国学者对它进行了广泛而深入的研究。     

可满足性问题有解的充要条件

本文对布尔表达式的可满足性问题作了进一步的研究，证明了该问题的充要条件，本文把布尔表达式可满足性的“判定的问题”与它的“求解问题”区别开来。     

基于多Agent的可满足性问题求解系统研究

为了得到高效可扩展的可满足性问题求解方法,融合目前解决可满足性问题(SAT)的诸多最新策略:快速DPLL、启发式极性决策算法等,提出了一种基于多Agent(Multi-Agent)的可满足性问题(SAT)验证方法.该方法给出了基于多Agent的可满足性问题求解系统的总体结构、工作流程和消息协议,详细分析了有关Agent的结构原理,在JADF(Java Agent development framework)基础上设计出智能仿真模型,通过实例研究表明该方法比传统的一般性求解方法精度高、速度快,且有较好的扩展性和可移植性.     

EDA领域中可满足性问题求解方法研究

可满足性问题是理论计算机和人工智能中的著名问题,很多问题都可以通过可满足性求解方法解决.对EDA领域中可满足性问题的求解技术进行了研究.总结了目前主要的求解方法,并对不同的方法进行了详细的分类和比较.讨论了该领域研究中存在的问题,并指出了近期研究热点和未来发展趋势.     

求解多文字可满足SAT问题的置信传播算法

可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得合取范式公式中每个子句至少有一个文字为真.多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得CNF公式中每个子句至少有两个文字为真.显然,此问题仍然是一个NP难问题.为了研究解决多文字可满足SAT问题的算法,引入随机实例产生模型,设计求解多文字可满足SAT问题的置信传播算法.最后,用实例模型产生了大量数据进行实验验证,结果表明:该算法求解多文字可满足SAT问题的性能优于其他启发式算法.     

可满足性问题的研究综述

对SAT问题及其各种约束子问题进行分类并给出具体定义,着重介绍常规SAT问题、最大可满足性问题（MAX—SAT）和参数化SAT问题的相关算法,并对参数算法中运用的技术进行分析和比较,提出一些SAT问题研究中值得关注的几个方面。     

基于改进的遗传算法求解可满足性问题

遗传算法(GA)是由Holland提出的一种基于进化论的仿生算法,非常适于求解最优化问题.为了更好地利用SGA求解SAT问题,在将SAT问题等价转换为{0,1}n上的多项式是否存在零点的判断问题基础上,将局部搜索算法(LSA)与SGA相结合,给出一种求解3-SAT问题的改进混合遗传算法(MHGA),并通过对随机大规模3-SAT问题实例的实际求解验证了MHGA的可行性与有效性.     

可满足性问题全部解的求解算法

SAT问题在人工智能、计算机基础理论研究和人工智能等领域有着广泛的应用,近年来,证明该问题的可满足性取得了巨大的成功,但在求出SAT问题的所有解方面还有待进一步研究。利用一个简单的变换,将可满足性（SAT）问题转化为多项式形式,然后根据命题逻辑的性质以及多项式的性质,得到一个求解出SAT问题所有解的算法。实验结果显示该算法是有效和可行的。     

求解可满足性问题的信息传播算法研究综述

信息传播算法来自统计物理,被广泛应用于人工智能各个领域,特别是求解组合优化问题时,具有良好的有效性。通过对信息传播算法的相关文献进行分析,综述了信息传播算法以及其相关应用的发展史,根据信息传播算法的发展,介绍了求解可满足性问题的信息传播算法相关概念,主要涉及到警示传播算法、置信传播算法和调查传播算法,描述了三种算法发展中出现的收敛性、有效性研究,分别综述了各个算法在相关领域的应用情况,并总结了信息传播算法的研究路径和应用方向。     

可满足实例的归结复杂度

GRB模型是一种随机约束满足问题模型,此模型具有精确的可满足相变现象。针对实验中出现的GRB模型在相变区域产生的可满足实例都是难解的现象,利用子句宽度和归结复杂度的关系证明了GRB模型在相变点附近产生的可满足实例对于树型归结证明具有指数下界。因此从理论上证明了在相变区域产生的可满足实例对基于归结的算法是难解的。     

RTL验证中的混合可满足性求解

RTL混合可满足性求解方法分为基于可满足性模理论(SMT)和基于电路结构搜索两大类.前者主要使用逻辑推理的方法,目前已在处理器验证中得到了广泛的应用,主要得益于SMT支持用于描述验证条件的基础理论;后者能够充分地利用电路中的约束信息,因而求解效率较高.介绍了每一大类中的典型研究及其所采用的重要策略,以及RTL可满足性求解方面的研究进展.     

求解可满足性问题全部解的改进多种群克隆免疫算法

对于可满足性问题全部解(ALLSAT问题)的求解而言,随着问题规模增大,现有算法逐渐变得不适用.针对不能有效求解ALLSAT问题的现状,提出了一种多种群克隆免疫算法,该算法采用小生境方法和位爬山算法进行优化,维持种群多样性,提高算法收敛速度进行了算法收敛性分析.ALLSAT问题的求解结果表明,该算法是非常有效的.     

求解难可满足性问题的混合算法

提出了一个求解难可满足性问题的简单混合算法．拟人和禁忌表两个策略被给出．数值实验表明，对于一类公认比较难的可满足性问题，该算法胜过目前据认为是最好方法之一的NOVELTY算法．     

一类布尔方程组的可满足性阈值研究*

以一类布尔方程组形式的NP问题可满足性阈值估计为研究目的,通过将高斯消去算法与摘叶算法相结合的方法给出了一种求解该问题的完全算法,并通过不同参数条件下对大量随机实例进行数值实验得到了原问题可满足性阈值的算法估计值。所得研究结果不仅首次给出了该问题的可满足性阈值估计,而且可以作为相关启发式完全算法的设计依据。     

可满足性问题中信念传播算法的收敛性分析

信念传播算法是基于因子图模型的消息传递算法,通过图中的边,将消息从一个结点传递给另一个结点,以高概率地确定部分变量的取值,这种方法被实验证明在求解可满足性问题时非常有效.然而,目前还未对其有效性从理论角度给予解释.通过对信念传播算法的收敛性分析,试图从理论上解释算法的有效性.在信息传播算法的信息迭代方程中,参数的取值范...     

基于DNA折纸术求解可满足性问题的计算模型

DNA折纸术是一种全新的DNA自组装方法,具有可编程性、纳米可寻址性等优点,被广泛地应用于DNA计算中.利用DNA折纸术可折叠出特殊结构的特点,在DNA折纸基底上设计了一种求解可满足性问题的计算模型,该模型采用分子信标原理,通过观察荧光的明灭排除非解,从而找出可满足性问题的解.最后通过实例和模拟仿真表明了模型的可行性.