搜索结果: 1-8 共查到“算法理论 SAT”相关记录8条 . 查询时间(0.053 秒)
近日，计算机科学与工程学院（网络空间安全学院）2017级本科生和肖鸣宇教授撰写的论文“A Fast Algorithm for SAT in Terms of Formula Length”被计算机科学理论方向重要国际会议SAT 2021接收，彭俊强为论文第一作者。SAT会议（The International Conferences on Theory and Applications of S...
基于SAT的电路错误定位方法研究进展
形式化验证 错误定位 布尔可满足性 可满足性模
2013/6/18
随着VLSI芯片复杂度不断增加，功能验证与调试已占到整个芯片设计周期的60%以上。而错误的定位往往消耗大量的时间与精力，因此迫切需要一种高效的方法诊断与定位电路中的错误。针对近年来出现的许多电路错误定位方法，介绍了电路错误诊断方法的分类与工作流程，深入分析了基于SAT的错误定位方法的基本原理；对各种算法进行了概述评论，并简要介绍了在不可满足子式求解方面所做的一些研究工作，而不可满足子式能够显著提高...
基于寻找可满足2SAT子问题的SAT算法
SAT问题 2-SAT子问题 2-SAT算法
2010/2/1
可满足问题（SAT）是一个NP-Hard问题。提出了一种求解SAT的新算法（FFSAT）。该算法将SAT问题转换为寻找一个可满足的2-SAT子问题。SAT问题虽然是NP完全问题，但是当所有子句长度不大于2时，SAT问题可以在线性时间求解。使用2-SAT算法-BinSat求解2-SAT子问题，当它不满足时，根据赋值选择新的2-SAT子问题。实验结果表明，采用本算法的结果优于UnitWalk。
一种规约于可满足性问题（SAT）的知识推理算法
知识结构 知识推理 可满足性问题（SAT）
2009/11/4
传统的知识推理算法主要依赖于通用的定理证明器，因此会有明显的组合爆炸问题和半自动化问题，只能处理小规模的问题。在文[1]中，给出了一个实用而紧致的知识的语义模型——知识结构（knowledge structure），并给出相应的利用BDD（Binary Decision Diagram）的符号化计算方法，实验表明这种基于BDD的算法比传统方法有很大的优势，但这种基于BDD 的方法在计算规模大的例子...
基于分组的启发式SAT新算法——DC&DS算法
等价性验证 布尔可满足性 二叉判决图
2009/7/17
目前提高求解SAT问题完全算法的计算效率问题已成为挑战性研究问题。提出了一种基于启发式分组的SAT完备算法。启发式分组策略将一个全局搜索问题，转为局部搜索问题。并将该策略引入到结合BDD与SAT算法的形式验证中，与一般的启发式SAT算法相比，该算法在求解速度和求解问题的规模等方面都明显地改进了，实验结果表明了该算法的可行性和有效性。
求解SAT问题的拟人退火算法
SAT问题 模拟退火算法 拟人
2007/12/27
该文利用一个简单的变换，将可满足性（SAT）问题转换为一个求相应目标函数最小值的优化问题，提出了一种用于跳出局部陷阱的拟人策略.基于模拟退火算法和拟人策略，为SAT问题的高效近似求解得出了拟人退火算法(PA)，该方法不仅具有模拟退火算法的全局收敛性质，而且具有一定的并行性、继承性.数值实验表明，对于本文随机产生的测试问题例，采用拟人策略的模拟退火算法的结果优于局部搜索算法、模拟退火算法以及近来国际...
求解SAT问题的局部搜索算法及其平均时间复杂性分析
2007/12/27
SAT问题在人工智能、VLSI设计和计算理论等领域有着广泛的应用
背景.近年来,局部搜索算法在求解SAT问题时得到了巨大的成功.本文除提
出了多种改进策略之外,还对一般局部搜索算法进行了平均时间复杂性分析.