导读:本文包含了布尔可满足性论文开题报告文献综述及选题提纲参考文献，主要关键词:现场可编程门阵列,布尔可满足性,加强约束,不完全算法
布尔可满足性论文文献综述
马柯帆,肖立权,张建民,黎铁军,周善祥[1]（2018）在《加强约束的布尔可满足硬件求解器》一文中研究指出利用现场可编程门阵列固有的并行性和灵活性,提出在硬件可编程平台上基于随机局部搜索算法的布尔可满足性求解器,用于求解大规模的布尔可满足性问题。相对其他求解器,该求解器的预处理技术能极大提高求解效率;其变元加强策略避免了同一变元被反复连续翻转,降低了搜索陷入局部最优的可能。评估结果表明,求解器最多能处理32 000个变元/128 000个子句的实例。相比当前同类型的求解器,其求解效率明显提高。(本文来源于《国防科技大学学报》期刊2018年06期）
吕逸杰,刘芳,周婷,艾江俊,巫光福[2]（2018）在《随机多比特翻转算法求解布尔多项式方程组可满足性问题》一文中研究指出布尔多项式方程组求解问题是数学与计算机科学中的难解之一,极大布尔多项式方程组可满足性问题是一般布尔多项式方程组求解问题的扩展问题.为了解决极大布尔多项式方程组可满足性问题,首先,提出了一种可证明是否存在满足全部函数为0的解的贪婪算法,结果是不存在满足256个函数全部为0的解;其次,提出了一种基于低密度奇偶校验码,比特翻转译码算法与随机数相结合的随机多比特翻转算法.(本文来源于《江西理工大学学报》期刊2018年01期）
候琳珊,李德[3]（2017）在《基于极大布尔多项式方程组的可满足性问题研究》一文中研究指出在选定的256个含有128个变量的布尔多项式中,我们通过对每个变量个数的统计,分析它们各自出现的频率,分类并对具有相同特征的变量进行赋值,简化变量个数,寻找到一组x_1,x_2,(43),x_(12) _8的赋值(其中x_i的取值均在GF(2)中)使得f_1,f_2,(43),f_(12) _8在这组变量的赋值下函数值取值为0的个数最多。通过上述赋值,我们确定出9个变量的取值,即x _(18),x_(33),x_(35),x _(45),x_(59),x _(63),x_(84),x _(96),x_(101)。对剩余的14个变量和256个多项式的奇偶项进行分析和处理,最终确定出14个变使得多项式为0的个数最多。(本文来源于《计算机产品与流通》期刊2017年10期）
郭莹[4]（2017）在《布尔可满足性问题研究综述》一文中研究指出布尔可满足性(简称SAT)问题是研究最广泛的NP-完全(简称NPC)问题之一。编码、预处理和求解算法是SAT问题求解的3个关键技术,近年来涌现了大量成果。SAT问题广泛应用在生产和生活中,SAT求解技术的健壮性和综合性能迫切需要进一步提升。从SAT问题分类、SAT问题应用领域、研究现状及面临的挑战等方面对相关研究成果进行梳理。(本文来源于《软件导刊》期刊2017年05期）
郭莹[5]（2016）在《求解布尔可满足性问题的关键技术研究》一文中研究指出布尔可满足性(简称SAT)问题是研究最广泛的NP-完全(简称NPC)问题之一。SAT问题不仅在数理逻辑和计算理论研究中占据着重要的位置,而且被越来越多地应用于计算机科学、人工智能和实际生产等领域,从而吸引了国内外众多研究者的关注。编码、预处理和求解算法是SAT问题求解的叁个关键技术,近年来涌现出了大量成果。然而除非P=NP,否则不存在最坏情况下多项式阶时间复杂度的SAT求解算法,设计出高效可行的SAT求解方法至今仍是研究的热点。本文围绕预处理和求解算法两方面进行了系统研究,针对不同类别问题的特点,在已有方法基础上提出了一系列改进策略和新方法,并通过理论分析和实验进行了有效性验证;最后以关系数据库视图更新的注释传播NP类问题为例,研究了归约到SAT问题的编码方法。本文工作主要包括:(1)为了提高预处理的化简能力和求解成功率,缩减求解过程的时间消耗,在目前得到广泛应用的预处理方法SATELITE基础上,提出了一种基于解析子句冗余属性状态约束的变量消除解析化简方法(RCS-VER),和一种基于冲突检测和学习的二元子句探针化简方法(CBCP),并基于变量表现特征分别针对变量消除解析和探针规则的特点提出了相应的变量选择启发式策略(HVC-VER和HVC-PRB),实验验证了以上方法和策略在应用类和组合类SAT问题实例上的可行性和有效性,其预处理性能和求解性能整体上优于改进前的SATELITE。(2)为了充分发挥重启策略对确定性CDCL求解器的作用,首先选取具有代表性的重启策略进行了实验对比分析,然后从“何时重启”和“何处重启”两个新的角度提出了相应的改进策略。一是根据平均冲突决策层次、决策层次冲突次数、冲突间决策次数、冲突间赋值变量数等参数对搜索分支进行局部求解状态评价,提出了相应的动态启发式When重启策略;二是基于变量后继决策数、变量后继赋值变量数、变量重启次数等参数提出了动态启发式Where重启策略;最终在流行的MiniSAT求解器基础上综合实现了 2WSAT(When&Where SAT)求解算法,实验验证了 2WSAT在应用类和组合类SAT问题实例上的可行性和有效性,其求解性能整体上优于标准的MiniSAT。(3)为了进一步研究和拓展随机类SAT问题实例的求解算法,将可满足性问题转化为一个求相应目标函数最小值的组合优化问题,对标准人工蜂群(简称ABC)算法进行离散化设计,首次将ABC算法设计应用到SAT问题的求解中,改进了初始解、适应度函数、邻域选择、新解生成、跟随蜂选择等策略,引入了禁忌搜索思想,提出了一个新的SAT求解算法(ABCSAT),实验验证了 ABCSAT在随机类可满足SAT问题实例上的可行性和有效性,平均在求解成功率、求解时间和内存消耗等方面优势明显。(4)为了进一步拓展SAT问题求解的应用领域,将关系数据库视图更新注释传播中的视图副作用、来源副作用、注释放置叁类基本问题的NP类问题转换为SAT问题,研究了 SAT问题的归约和编码方法。(本文来源于《东北大学》期刊2016-04-01）
郭文生,杨国武,李晓瑜,高敏[6]（2015）在《基于满足性判定的布尔网络环求解算法》一文中研究指出环是布尔网络状态转换过程中的稳定态,在模式检测、基因调控网络和可达性分析等领域都有重要的意义。计算布尔网络状态转换中的所有环是一个NP完全问题。该文基于全解布尔满足性判定(SAT)算法,设计了一种求解所有小于等于指定步长环的算法。算法基于布尔网络的状态转换函数和状态环属性生成合取范式形式(CNF)的问题集,通过融合冲突子句学习(CDCL)、非时序回退、阻塞子句和变量分类等技术,降低算法的计算复杂度。实验结果表明,该算法能够高效地计算指定步长的环。对于无法计算所有环的复杂网络,指定步长计算环的方式将更有应用价值。(本文来源于《电子科技大学学报》期刊2015年06期）
范全润[7]（2015）在《基于分治的布尔可满足性判定》一文中研究指出SAT是最着名的NPC问题。NPC类问题有两方面的特性,首先,这类问题的解可以在多项式时间复杂度内得到验证。其次,其它NP问题可以在多项式时间内转换为NPC问题来求解。因此,SAT判定技术的研究具有重要的理论意义。SAT判定技术还具有很大的实用价值。它可以应用到包括人工智能规划、模型分析、定理证明、软件验证和软件测试、软件发布中的包管理等领域。在电子设计自动化中,SAT可用于电路的逻辑综合、布尔匹配、电路等价性验证、模型检验、自动测试用例生成、FPGA的布局布线、设计调试与诊断等。本文研究SAT判定问题,SAT判定问题的时间复杂度是指数阶的,这意味着如果问题的规模较大时,要完成SAT判定会非常困难。研究利用分治的思想,通过将复杂的SAT的判定问题划分为多个规模更小的子问题来求解,在划分代价较小的情况下,利用这一方法来降低可满足性判定的复杂度。通过系统深入的理论分析和实验研究,取得了如下创新性成果:提出了CNF形式的布尔公式的子句组划分的概念,并证明了布尔公式的可满足性问题可以转化为子句组的可满足性问题来求解。给出了一种从CNF公式产生子句组划分,以及利用子句组划分来进行SAT判定的方法。对于不能直接产生子句组划分的公式,提出利用聚类方法,将子句聚类成多个簇,把包含共同变量多的子句聚类到同一个簇,包含共同变量少的子句聚类到不同的簇,将不同簇之间的共同变量作为割变量,通过对每个簇单独判定,必要时再判断割变量的取值是否冲突来判定公式的可满足性。由于传统的聚类方法并不能很好地适应CNF子句的聚类要求,因此本文针对CNF公式的特点,提出一种两阶段的聚类方法,先用基于连接的方法来产生初始聚类,在一定程上避免聚类的局部最优性,然后再用基于簇间相似度进行合并的方法来生成最终的聚类结果。算法的第一阶段通过指定聚类结果簇与原始簇个数的比值来确定生成的簇的个数,第二阶段则通过相似度阈值来确定何时终止聚类,因此无需指定最终生成的簇的个数。在聚类完成之后,如果要消去所有簇之间的共同变量,将所有的簇都划分开,在某些情况下,由于公共变量太多,可能需要付出太大的代价。为解决这一问题,本文提出将聚类结果中的簇作为顶点,用簇间的公共变量来标记边,将聚类结果变换成一个无向图,然后利用无向图最小割的方法来寻找将簇划分成两组的最小割变量集,以产生子句组划分。在某些情况下,将问题变换为CNF公式,可能会导致一些结构信息的丢失。针对组合电路的等价性验证问题和AIG电路的特点,本文提出一种方法,直接在电路上通过电路的特点进行推理来判定Miter电路的可满足性,从而充分利用应用领域知识来提高AIG电路的可满足性判定效率。(本文来源于《西安电子科技大学》期刊2015-04-01）
张建民,黎铁军,徐炜遐,庞征斌,李思昆[8]（2015）在《求解布尔不可满足子式的消解悖论算法》一文中研究指出求解布尔不可满足子式在超大规模集成电路设计与验证领域都具有非常重要的理论与应用价值,帮助EDA工具迅速定位错误与不一致。针对求解不可满足子式的非完全方法,提出了消解悖论与悖论解析树的概念,在此基础上提出一种启发式局部搜索算法。该算法根据公式的消解规则,采用局部搜索过程直接构造证明不可满足性的悖论解析树,而后递归搜索得到不可满足子式;算法中融合了布尔推理技术、动态剪枝方法及蕴含消除方法以提高搜索效率。基于随机测试集进行了实验对比,结果表明提出的算法优于同类算法。(本文来源于《国防科技大学学报》期刊2015年01期）
郭文生[9]（2014）在《布尔满足性判定算法研究》一文中研究指出布尔满足性判定问题是多个不同学科的交叉问题,它是一类着名的NP-完全问题。但是,随着布尔满足性判定算法性能的不断提升,它已经被大量的应用于实际问题的求解,如组合电路等价性检测、自动测试模板生成、软件模式检测、满足模块定理证明、计算生物学和自动规划等。大量具有不同特性的布尔满足性判定算法被设计和优化,以实现对实际问题的快速求解。但是,部分问题求解的时间复杂度和空间复杂度还有待进一步降低,很多难实例问题仍然在有限的时间内无法求解。针对特定问题类的高效布尔满足性判定算法一直是计算机及人工智能领域的热点研究问题之一。本文在深入研究布尔满足性判定算法的基础上,针对不同的问题进行了建模和算法设计,其主要研究内容分为四部分。1、针对Model RB模型的特性,通过集合和图的方式对问题进行了形式化建模和描述,融合完全布尔满足性判定算法和随机布尔满足性判定算法的不同优势,实现了高效的完全布尔满足性判定算法。基于完全布尔满足性判定算法的基本搜索流程,提出了基于互斥集和关联集的搜索判定算法。在搜索过程中,根据动态生成的子句集构造搜索树、选择决策变量并确定回退机制。为实现搜索过程中的快速冲突回退,使用随机算法获得图中的最大团,并利用最大团中的节点构造初始搜索树。实验结果显示,算法在Model RB模型和图着色问题实例中具有较好的性能。2、随着人们对基因认识的不断深入和基因序列提取能力的不断增强,计算生物学对基因的研究已经从单基因的性质研究逐渐转向对基因调控网络的动态特性研究。在基因调控网络研究中的一个重要问题是吸引子的求解问题,吸引子代表基因网络的稳定状态,一个吸引子表示一种细胞类型。基于同步布尔网络建模的方式,将基因调控网络的动态调控过程转化成了同步布尔网络的状态转换图。为降低状态转换图中吸引子的求解复杂度,以布尔网络中的强连通分支为单位将布尔网络划分成了多个块,各个块之间形成有向无环的依赖关系。算法通过计算每一个块的局部吸引子来获得整个网络的吸引子。在计算局部吸引子时,算法通过展开布尔网络转换函数的方式将吸引子求解问题转换成布尔满足性判定问题进行求解。实验结果表明,基于分块的吸引子求解算法针对复杂的基因调控网络具有显着的优势。3、为充分利用计算机多核的处理能力,实现高效的问题求解,并行计算已经成为一种必然的软件设计趋势。在深入研究并行布尔满足性判定算法的基础上,结合基于分块的算法特性,设计并实现了两种并行的吸引子求解算法:基于块的并行算法和基于局部吸引子的并行算法。基于块的并行算法使用空间划分的方式实现并行布尔满足性判定求解,而基于局部吸引子的并行算法在空间划分的基础上实现了负载均衡。基于块的并行算法在计算完第一个节点块的所有局部吸引子后,将局部吸引子平均分配给所有CPU的核进行后续的节点块计算。基于局部吸引子的并行算法计算完一个局部吸引子就会产生一个消息,通知空闲CPU核进行后续的计算。实验结果表明,并行吸引子求解的性能优于串行求解的性能,基于局部吸引子的并行算法优于基于块的并行算法。特别是当CPU的核数较多时,基于局部吸引子的并行算法优势更加突出。4、布尔网络稳定态的计算是一个NP完全问题,大量的实例无法在有限的时间内获得所有的稳定状态。为能够对问题进行初步的分析,提出了一种计算小于等于给定环长的所有稳定态的算法。算法基于边界模式检测技术对问题进行建模,基于变量分类、蕴含图的决策变量生成阻塞子句等技术对布尔满足性判定全解算法进行了优化。实现结果表明,算法对于环长分布比较均匀的布尔网络具有较低的计算复杂度,特别是对于无法计算所有环的复杂网络,算法更具有应用价值。(本文来源于《电子科技大学》期刊2014-09-15）
王艺源[10]（2014）在《布尔可满足关键问题研究》一文中研究指出命题公式的可满足问题是首个被证明为NP的问题，而且是计算机科学中很多领域的重要问题，包括计算机科学基础理论、人工智能、数理逻辑。在1997年和2003年人工智能会议上提出了SAT问题面临的十大挑战性问题，在2001年和2007年两年都对当时的SAT问题现状进行了完整的总结。这十大挑战性问题的提出对SAT问题的理论研究和算法改进起到了很强的推动作用。目前的SAT问题主要应用在电子设计自动化中，在此同时，许多世界上现实的实际问题都可以转化为SAT问题。很多的研究者也投入在SAT高效的求解算法的研究中，主要包括两大算法：完备求解算法和不完备求解算法。完备算法的SAT求解算法主要是基于DPLL求解的，该类算法能够证明命题公式是否有解，但是效率比较低；而不完备算法主要是通过局部搜索算法，进行求解，基于局部搜索求解的，该类算法可以很快的找到解，但是当没有找到解退出的时候，不能说明命题公式是否有解。随着发展，扩展出一些SAT的分支问题：最大可满足问题、量化的布尔公式、可满足性模块理论等。在SAT问题中，骨架变量是在所有可满足赋值中都恒取定值的变量，骨架变量的规模与SAT问题中的搜索规模有着密切的关系。这种特性可以用来减少一些问题的复杂性，所以骨架变量在一些SAT问题中，可以进行一些优化，例如故障诊断、随机3-SAT问题、概率信息传递算法等。因为骨架变量的这些优势，目前提出了很多计算骨架变量的算法，这些算法主要是基于迭代、基于分块、基于不可满足核的算法。其中，也可以组合这些思想，变成混合算法进行求解骨架变量。本文主要利用改进的变量选择策略应用到基于迭代的骨架变量算法中。首先利用基于DPLL的SAT完备算法中层的概念，作为变量选择策略，应用到骨架变量的求解中。利用层信息动态地选择变量去求解骨架变量，提高算法的效率：可以连续地运用可满足的增量信息，还可以尽早地加速削减搜索空间。然后本文回顾了在SAT不完备算法中的邻居策略。本文把基于邻居策略的思想，利用到骨架变量的求解中，通过尽早地找到骨架变量，减少表达式的复杂性，加速了算法的求解。实验结果表明，两种新的变量选择策略，都可以提高算法的性能，对比两者可以得到，基邻居的策略表现出更好的性能。(本文来源于《吉林大学》期刊2014-04-01）
布尔可满足性论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
布尔多项式方程组求解问题是数学与计算机科学中的难解之一,极大布尔多项式方程组可满足性问题是一般布尔多项式方程组求解问题的扩展问题.为了解决极大布尔多项式方程组可满足性问题,首先,提出了一种可证明是否存在满足全部函数为0的解的贪婪算法,结果是不存在满足256个函数全部为0的解;其次,提出了一种基于低密度奇偶校验码,比特翻转译码算法与随机数相结合的随机多比特翻转算法.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
布尔可满足性论文参考文献
[1].马柯帆,肖立权,张建民,黎铁军,周善祥.加强约束的布尔可满足硬件求解器[J].国防科技大学学报.2018
[2].吕逸杰,刘芳,周婷,艾江俊,巫光福.随机多比特翻转算法求解布尔多项式方程组可满足性问题[J].江西理工大学学报.2018
[3].候琳珊,李德.基于极大布尔多项式方程组的可满足性问题研究[J].计算机产品与流通.2017
[4].郭莹.布尔可满足性问题研究综述[J].软件导刊.2017
[5].郭莹.求解布尔可满足性问题的关键技术研究[D].东北大学.2016
[6].郭文生,杨国武,李晓瑜,高敏.基于满足性判定的布尔网络环求解算法[J].电子科技大学学报.2015
[7].范全润.基于分治的布尔可满足性判定[D].西安电子科技大学.2015
[8].张建民,黎铁军,徐炜遐,庞征斌,李思昆.求解布尔不可满足子式的消解悖论算法[J].国防科技大学学报.2015
[9].郭文生.布尔满足性判定算法研究[D].电子科技大学.2014
[10].王艺源.布尔可满足关键问题研究[D].吉林大学.2014