检索结果-内蒙古大学图书馆

软件工程与应用 2016年第1期5卷 47-55页

作者：刘文秀江建国李千卉辽宁师范大学数学学院辽宁大连

针对命题公式φ(CNF形式)的可满足性问题的求解效率问题,基于对dpll完全算法的学习和在不同形式下对子句文字排序处理的研究,提出了一种新的求解SAT问题的算法。新算法根据子句长度对命题公式φ进行分组,并根据变量出现次数进行初始排序... 详细信息

针对命题公式φ(CNF形式)的可满足性问题的求解效率问题,基于对dpll完全算法的学习和在不同形式下对子句文字排序处理的研究,提出了一种新的求解SAT问题的算法。新算法根据子句长度对命题公式φ进行分组,并根据变量出现次数进行初始排序,然后考虑变量中正负文字出现的次数,并对次数高的进行赋值。算法实例表明:新算法能减少求解过程中规则使用次数,减少求解步骤,尽早剪除不满足解空间,从而有效提高求解效率。

关键词： dpll算法启发式策略可满足性问题

来源：评论

学校读者我要写书评

暂无评论

基于随机方法和优化的dpll算法的测试用例自动生成技术研究

引用

化工自动化及仪表 2016年第9期43卷 927-931,1008页

作者：查敬芳白涛胡立生上海交通大学电子信息与电气工程学院上海200240 深圳中广核工程设计有限公司广东深圳518172

提出一种基于随机方法和优化的dpll算法的测试用例自动生成技术,并以基于FPGA的核电仪控系统为对象进行了验证。该方法能验证HDL描述符合设计规范的要求,代码覆盖率较好,所提方法在解决大规模问题时效率有所提升,尤其是对于可满足性问题... 详细信息

提出一种基于随机方法和优化的dpll算法的测试用例自动生成技术,并以基于FPGA的核电仪控系统为对象进行了验证。该方法能验证HDL描述符合设计规范的要求,代码覆盖率较好,所提方法在解决大规模问题时效率有所提升,尤其是对于可满足性问题,效率提升非常显著。

关键词：测试用例 SAT问题 dpll算法核电仪控系统

来源：评论

学校读者我要写书评

暂无评论

基于软硬件协同计算的SAT求解器设计与实现

基于软硬件协同计算的SAT求解器设计与实现

引用

作者：奚瑞兰州大学

学位级别：硕士

布尔可满足性问题(Boolean Satisfiability Problem,SAT)是一个经典的判定问题,也是历史上首个被证实的NP问题。很多现实问题被证明可以转换为SAT问题去求解,例如人工智能中的轨迹规划和资源调度、集成电路中的模型检测和等价性验证等,... 详细信息

布尔可满足性问题(Boolean Satisfiability Problem,SAT)是一个经典的判定问题,也是历史上首个被证实的NP问题。很多现实问题被证明可以转换为SAT问题去求解,例如人工智能中的轨迹规划和资源调度、集成电路中的模型检测和等价性验证等,因此,SAT问题一直是理论计算机科学领域中的研究重点。随着求解SAT问题的技术不断提高,软件求解器的发展已经趋于成熟,并具有非常优越的性能,但依然难以有效求解某些类型的SAT实例。而集成电路技术的不断发展也促进了硬件求解器的进步,基于硬件的求解方式虽然在复杂算法的实现上具有一定的局限性,但是它可以充分利用硬件平台的特点和资源,对算法的部分模块进行并行化的处理,以此设计可重构硬件SAT求解器。针对两种求解器的特点,本文结合应用型求解方式进行SAT硬件求解器的设计。首先,在传统dpll算法的基础上加入随机排序和随机赋值策略,以此提高平均求解速度。采用异步控制机制,设计高性能可重构双链电路,用于控制dpll算法的前进和回溯。使用布尔约束传播技术来加速变量的推导过程,通过分析蕴含推理的原理,编写解析器自动生成不同SAT问题的蕴含公式,提高求解效率。其次,针对目前软硬件协同处理机制中主-协处理器同步困难、通信时间较长等问题,采用将处理器系统与现场可编程门阵列相结合的ZYNQ平台进行设计,将与具体SAT问题无关的模块放在硬件上并行加速,与具体SAT问题相关的模块放在软件上便于修改配置,CPU与FPGA之间通过AXI总线进行通信,最后设计实现了一个基于软硬件运行时协同计算的SAT求解器。由于本文设计的硬件部分是一个最多可求解200个变量的可重构计算架构,求解具体SAT问题时只需要在软件部分进行配置即可,从而避免了为每个SAT实例进行耗时的FPGA综合、布局布线等步骤。通过测试大量的SAT实例,并与软件求解器的求解结果进行对比,证明了该求解器的正确性。

关键词：布尔可满足性问题软硬件协同计算异步电路 dpll算法 ZYNQ平台

来源：评论

学校读者我要写书评

暂无评论

一种改进的dpll算法研究及在集成电路设计验证中的应用

一种改进的DPLL算法研究及在集成电路设计验证中的应用

引用

作者：余德克北京大学

学位级别：硕士

电子设备的可靠性取决于其所采用的软硬件系统，归根到底，是其可靠的硬件基础——集成电路。集成电路的发展同时也促进计算机技术和通信技术的飞速发展，为此，保证集成电路拥有可靠的性能具有重要的现实意义。随着近年来可满足性问题... 详细信息

电子设备的可靠性取决于其所采用的软硬件系统，归根到底，是其可靠的硬件基础——集成电路。集成电路的发展同时也促进计算机技术和通信技术的飞速发展，为此，保证集成电路拥有可靠的性能具有重要的现实意义。随着近年来可满足性问题（Boolean Satisfiability Problem，SAT）求解技术的研究发展，基于SAT求解器引擎的验证方法成为近年来集成电路验证领域一个新的研究热点。\n dpll（Davis-Putnam-Logemann-Loveland）算法是目前求解SAT问题最有效的算法，也是当前大部分SAT求解器的算法核心。尽管当前的SAT求解器已经集成了许多启发式搜索技术，但是仍然存在如下问题:\n 在DPL分支决策过程中，分支的选择仍然具有一定的盲目性，选择一个坏的分支进行决策推理很容易造成搜索树空间的增大，从而极大的影响算法的整体求解性能。\n 针对上述问题，本文在对dpll算法开展深入研究后，提出了一个改进方案，主要完成的工作如下:\n 本文提出了一种带自适应噪声调整机制的混合SAT算法，并称之为ANHSAT。在ANHSAT中，将带有自适应噪声调整机制的局部搜索算法WalkSAT作为dpll算法的前驱，将WalkSAT产生的近似解作为dpll算法在分支决策时的优先参考子空间进行搜索。dpll算法在选择变量准备分支推理时会优先分支近似解中的变量极性。实验结果表明，在与三种其他的SAT求解器比较中，提出的算法ANHSAT不仅在针对软硬件形式化验证领域的问题上表现出高效的性能，同时在其他实际问题（如人工智能规划、FPGA路由等）方面的求解上也表现出良好的性能。

关键词：集成电路验证可满足性问题 dpll算法混合算法自适应噪声

来源：评论

学校读者我要写书评

暂无评论

基于变量特征的CDCL算法中分支策略优化研究

基于变量特征的CDCL算法中分支策略优化研究

引用

作者：艾森阳西南交通大学

学位级别：硕士

可满足性问题(Satisfiability Problem,SAT问题)是数理逻辑中的一个经典问题,也是自动推理的一个重要研究方向。在理论应用方面,许多的NPC(Non-deterministic Polynomial Complete)问题如图着色问题、欧拉回路问题和旅行商问题等,都可... 详细信息

可满足性问题(Satisfiability Problem,SAT问题)是数理逻辑中的一个经典问题,也是自动推理的一个重要研究方向。在理论应用方面,许多的NPC(Non-deterministic Polynomial Complete)问题如图着色问题、欧拉回路问题和旅行商问题等,都可以转化成SAT问题进行求解。在实际应用方面,如计算机辅助设计与制造领域和人工智能领域中的一些现实问题,通过逻辑形式化方法可以转化为SAT问题进行求解。另外,形式化验证中的一个不可缺少环节就是逻辑公式可满足性的判定。因此,研究SAT问题不仅具有重要的理论价值而且具有广泛的应用前景。目前,求解SAT问题的算法主要分为完备算法和不完备算法两种。完备性算法主要基于穷举和回溯思想,不完备算法主要基于局部搜索思想。基于dpll(Davis Putnam Logemann Loveland)算法发展而来的CDCL(Conflict driven clause learning)算法是具有代表性的完备算法,也是目前求解SAT问题的一种主流算法。它的求解结构主要包括预处理、子句学习、分支决策和重启等模块。在CDCL算法求解框架中,随着搜索的进行求解器会不断地记录产生冲突的原因,能够避免后续搜索过程进入相同的冲突空间。研究结果表明,基于冲突学习的能力是CDCL算法求解高效的关键因素。在CDCL算法框架下,针对基于冲突分析的分支决策环节,本文主要做了以下两方面的工作:1.为减少求解器在分支决策环节出现过多随机赋值的现象,本文在VSIDS(Variable State Independent Decaying Sum)分支策略的基础上,融入了冲突次数和变量所在子句的LBD值两种特征,提出了一种基于变量特征的分支策略,称为BVA(Breaking the Balance of Variable Activity)分支策略。BVA分支策略在分支决策过程中不改变变量活性值的整体增长趋势,只是小幅度地提升了部分变量的活性值。这样不仅保留了VSIDS分支策略的原有优势,而且更有利于减少VSIDS分支策略的随机性,使分支变量的选择更准确。2.基于上面的工作,将BVA分支策略形成算法,嵌入到著名的求解器Glocose4.1和2018年国际竞赛冠军求解器Maple＿LCM＿Dist＿Chrono BT中,分别形成了Glocose4.1+BVA求解器和Maple＿LCM＿Dist＿Chrono BT+BVA求解器。在实验部分,实验选择2017-2019年的竞赛例作为测试例。通过实验对比分析表明改进的两个求解器在求解效率和求解能力方面均优于原版求解器,尤其在求解不可满足性问题上表现出明显的优势。

关键词： SAT问题 dpll算法 CDCL算法分支策略

来源：评论

学校读者我要写书评

暂无评论

基于CDCL求解器的分支策略和删除策略的研究

基于CDCL求解器的分支策略和删除策略的研究

引用

作者：刘姚西南交通大学

学位级别：硕士

SAT问题是计算机科学理论和人工智能中的著名问题。NP完全问题(NP-complete,NPC)排在千禧年七大难数学问题之首,许多NP完全问题都可以在多项式时间内转换为SAT问题进行求解。SAT问题广泛应用于数学定理证明、计算机软件与理论、工程技... 详细信息

SAT问题是计算机科学理论和人工智能中的著名问题。NP完全问题(NP-complete,NPC)排在千禧年七大难数学问题之首,许多NP完全问题都可以在多项式时间内转换为SAT问题进行求解。SAT问题广泛应用于数学定理证明、计算机软件与理论、工程技术、软件验证以及逻辑电路等价性验证等多个领域。因而SAT问题一直是国内外学者关注的热点问题,设计并实现求解SAT问题的高效算法具有重要的钻研意义和应用远景。dpll求解器开创了求解SAT问题的先河,但其算法自身的回溯机制对大规模问题的求解有一定程度的制约性。为了提升dpll算法的求解效率,国内外学者们进行了大量的研究,添加了一些关键技术。例如启发式分支策略、基于冲突分析和子句学习、非时序回溯、学习子句的删除和周期性重启等,形成了当前最流行的CDCL(Conflict-Driven-Clause-Learning,CDCL)求解器。基于CDCL算法结构,本文做了以下研究工作:一、借鉴VSIDS策略及其延伸策略的思想,研究变量的决策层和变量参与冲突的冲突次数对分支决策阶段的影响,在此基础上提出一种改进的启发式分支策略——基于变量决策层的启发式变量选择策略(HSVDL),为分支决策提供依据,从而引导求解器的搜索进程。二、在充分考虑学习子句的子句长度和变量的决策层对子句删除的影响后,为了充分发挥短子句在演绎过程中的优势,因此给出平均子句长度的定义,在删除策略中用于删除较长的学习子句。然后提出了一种新的学习子句删除策略——基于学习子句长度和LBD的删除策略(LLBD)。三、分别将所提出的HSVDL策略和LLBD策略形成相应算法,嵌入到著名求解器Glucose4.1中,得到新的求解器Glucose4.1+HSVDL和Glucose4.1+LLBD;将所提出的HSVDL策略和LLBD策略同时嵌入求解器Glucose4.1中,得到新的求解器Glucose4.1+HSVDL+LLBD。选择2017年和2018年SAT国际竞赛Main Track组的竞赛例进行测试,测试结果从成功求解个数、平均决策次数、平均冲突次数、平均重启次数、平均用时等多项指标与求解器Glucose4.1的测试结果进行对比分析,显示出了新的求解器的有效性及优势。

关键词： SAT问题 dpll算法 CDCL算法 HSVDL策略 LLBD策略

来源：评论

学校读者我要写书评

暂无评论

基于CDCL的SAT问题的分支启发式策略研究

基于CDCL的SAT问题的分支启发式策略研究

引用

作者：胡容西南交通大学

学位级别：硕士

命题逻辑公式的可满足性问题（SAT问题）是指给出一个合取范式,判断是否存在一组赋值使得这个合取范式可满足。SAT问题是计算机科学与工程、人工智能、计算机视觉和计算机辅助设计等领域的一个核心问题,它也是第一个被证明的NP完全（Non... 详细信息

命题逻辑公式的可满足性问题（SAT问题）是指给出一个合取范式,判断是否存在一组赋值使得这个合取范式可满足。SAT问题是计算机科学与工程、人工智能、计算机视觉和计算机辅助设计等领域的一个核心问题,它也是第一个被证明的NP完全（Non-Deterministic Polynomial-Complete,NPC）问题。正因为如此,研究SAT问题并提高求解器的效率是很有价值的。求解SAT问题的算法分为完备算法和不完备算法。完备算法的特点是在问题可满足时,给出一个模型;不可满足时,给出证明。基于完备算法的优点,本文以CDCL（Conflict Driven Clause Learning,CDCL）算法为框架,研究CDCL算法的以下主要流程:决策、冲突分析、学习子句和回溯之间的关系。SAT求解器的成功绝大多数归因于从错误赋值中学习的能力、快速地删除搜索空间以及首先集中在那些“重要”变量中[1]。故本文集中在CDCL算法中的决策和冲突分析上,取得的主要研究结果如下:1.当一个命题逻辑中的逻辑公式以CNF的形式输入到数据库时,从中选择“重要”变量的依据是变量出现的次数和包含该变量子句的长度。因为越短的子句越难满足,故优先考虑短子句,相应地,短子句中的变量就“重要”。由这些信息,给出变量的初始计分和排序方法。2.当发生冲突时,即当前赋值使得某些子句为不可满足子句,参与冲突的那些子句中对应的变量的价值高于没有参与冲突的,因而在这个阶段考虑由这些子句或者变量所携带的信息刻画变量的贡献值。根据参考文献中的实验数据分析看出指数级的增长效果较好,因此,根据学习子句长度的不同,进行分段,在每个段,给出一个常数加上一个指数函数的方法进行计分排序。3.根据以上研究结果提出一种新的分支启发式策略并运用在glucose4.0算法上,用2016和2017年SAT竞赛例子和SATLIB例子测试,根据效果修改参数。结果表明在一定程度上比原始求解器glucose4.0有所提高。

关键词： SAT问题 dpll算法 CDCL算法分支启发式策略

来源：评论

学校读者我要写书评

暂无评论

可满足问题求解算法dpll的优化技术研究

可满足问题求解算法DPLL的优化技术研究

引用

作者：刘文秀辽宁师范大学

学位级别：硕士

求解效率一直是可满足性问题(SAT)的研究热点,因为提高效率可以有效的扩大SAT的应用范围。长期以来,研究者们对此进行了不断地探索,并提出了多种算法,如Tableau、dpll、GRASP等。随着研究的进一步深入,人们发现dpll算法具有高效、易操... 详细信息

求解效率一直是可满足性问题(SAT)的研究热点,因为提高效率可以有效的扩大SAT的应用范围。长期以来,研究者们对此进行了不断地探索,并提出了多种算法,如Tableau、dpll、GRASP等。随着研究的进一步深入,人们发现dpll算法具有高效、易操作等优点,所以对dpll算法的优化与改进逐渐成为SAT求解算法的核心。本文在dpll算法的基础上,针对它在选取判定变量时过于随机的问题,提出了两种判定层优化技术。具体研究内容如下:1提出了基于变量个数的判定启发式策略。该策略是在对dpll完备算法的学习和不同形式下对子句文字排序处理研究的基础上提出的,它通过统计子句集中每个变量的出现次数,并考虑变量中正负文字的出现次数,然后挑选出次数最高的进行赋值。实例结果表明,应用该策略求解时可以有效简化实例的求解空间,减少求解步骤,尽早剪除不满足解空间,从而有效提高求解效率。2提出了基于文字分数的判定启发式策略。该策略是在考虑子句长短和变量正负出现对变量判定影响的基础上提出的,它通过对子句集中每一个文字设定一个分数,并将分值高的作为判定变量,同时在求解过程中,及时删除已满足子句。实例结果表明,该策略的提出有利于提高判定变量选取的准确性,可以有效避免一定的冲突,降低求解时间,使得求解效率显著提高。

关键词：可满足性问题 dpll算法判定层启发式

来源：评论

学校读者我要写书评

暂无评论

基于FPGA的实例型SAT求解芯片的设计与实现

基于FPGA的实例型SAT求解芯片的设计与实现

引用

作者：谌知学广西民族大学

学位级别：硕士

布尔可满足问题(SAT)作为第一个被证明的NP问题在许多方面有着重要的应用,该问题是人工智能、集成电路设计与验证、计算机科学、数理逻辑等领域中的核心问题,并且在计算机复杂性理论中有着十分重要的地位,作为NP问题,SAT问题无法在多项... 详细信息

布尔可满足问题(SAT)作为第一个被证明的NP问题在许多方面有着重要的应用,该问题是人工智能、集成电路设计与验证、计算机科学、数理逻辑等领域中的核心问题,并且在计算机复杂性理论中有着十分重要的地位,作为NP问题,SAT问题无法在多项式时间内求解,因此高效的SAT求解器的设计一直被世界各国的学者所重视,SAT求解算法分为完备算法和不完备算法,求解器分为软件求解器和硬件求解器,其中硬件求解器又分为实例型求解器和应用型求解器。本文给出了两种基于FPGA的实例型硬件求解器的求解框架,即基于电路特征的求解框架和基于dpll算法的求解框架,通过改变基于电路特征的求解框架中的激励模块实现了三种不同的求解方法,即顺序遍历激励求解、真随机数激励求解和伪随机数激励求解,并对三种求解方法的实验结果进行了对比和分析。对于基于dpll算法的求解器,本文创新地在求解电路生成前对变量选取顺序和变量赋值顺序进行了随机排序,并对同一实例生成多个求解电路进行多次求解,对不同次数的求解结果进行了分析,并将所有实例的求解结果与其他硬件求解器及软件求解器Minisat进行了分析和对比。

关键词：布尔可满足现场可编程门阵列合取范式真随机数伪随机数 dpll算法形式验证方法

来源：评论

学校读者我要写书评

暂无评论

基于CDCL的SAT问题求解算法研究

基于CDCL的SAT问题求解算法研究

引用

作者：易念西南交通大学

学位级别：硕士

人工智能领域中,研究命题逻辑公式的可满足性(SAT)问题具有十分重要的作用。随着科学、技术、社会等领域的发展,需要解决的SAT问题的规模变得越来越大,而传统单一的算法无法适应这些大规模的SAT问题。因此一些针对大规模的SAT问题的求... 详细信息

人工智能领域中,研究命题逻辑公式的可满足性(SAT)问题具有十分重要的作用。随着科学、技术、社会等领域的发展,需要解决的SAT问题的规模变得越来越大,而传统单一的算法无法适应这些大规模的SAT问题。因此一些针对大规模的SAT问题的求解器应运而生,如Chaff、zChaff、Minisa、Lingeling等诸多著名求解器。这些求解器都并非由单一的算法构建,而是在传统的dpll等算法的基础上构建的一套系统,如CDCL求解器,其包含多个决策过程,在算法过程中不断的改进学习和调整,以更为高效的解大规模的SAT问题。这些求解器主要分为如下几个部分,分别是变量决策、冲突分析、子句学习和回溯机制。而其中的变量决策过程在整个算法构架中占有十分重要的地位,一个好的变量决策策略可以减少冲突的产生,大量节省求解时间,因此研究变量决策过程的策略具有较为重要的意义。本文主要结合CDCL求解器构架,做了如下几个方面的研究工作：1、本文提出一种启发式策略,根据所给子句、文字数量和出现次数,定义文字相关系数、子句相关系数,进而对初始变量决策过程提供依据；2、基于定义的相关系数,给定冲突状态定义,根据冲突状态下的总的冲突数不断减少的原则,进而定义冲突稳定状态,根据冲突稳定状态制定回溯回退机制策略；3、基于以上两种策略,结合CDCL求解器形成求解SAT问题新算法(Conflict-SAT),并采用SAT竞赛中的问题以及TPTP问题库中旅行商问题进行实例测试,并对测试结果进行分析比较。

关键词：命题逻辑可满足性问题 dpll算法 CDCL Conflict-SAT

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：