一个关于Hamilton环（路）的多项式时间算法

该研究为Hamilton环路（道路）问题设计出了一个多项式时间算法,论证了它的正确性。根据该算法编制了程序,进行了大量的实例计算。文章公布了主要研究方法、过程、实验数据,以及粗略的算法步骤。详细的算法步骤和证明将在随后的论文中发表。由于Hamilton环路（道路）为著名的NP完全问题,而作者认为自己已彻底解决了NP复杂问题。     

IP Mesh网络的多约束QoS选路研究

多约束QoS路由算法一直是研究重点和难点,是一个有待解决的NP完全问题。针对IP Mesh网络的特点,设计出相应的完全图,并且推出了n个节点的完全图路径总数目公式。提出了一种CBFS_MCP算法,首先用Dijsktra最短路径算法对节点和边进行删减,将完全图简化,再在简化图上用类BFS算法通过“约束条件夹逼”和不断剪枝,寻找一条从起点s到终点t的符合两个约束条件的可行路径。实验结果表明CBFS_MCP算法有着良好的算法性能。     

MSP问题的一个求解算法

MSP问题是文献［1,2］提出的一个问题。研究表明［3］该问题对NP类问题有很强的表达能力。本文给出一个关于该问题的求解算法、复杂性分析,以及正确性证明。本文对于NP完全问题研究有重要意义。     

特殊形式和结构的MSP问题NP完全性研究

针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化.以简化证明为导引,提出一种特殊形式和结构的MSP问题.而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性,会极大影响进一步简化算法证明的研究意义.因此,提出的特殊形式和结构的MSP问题进行了NP完全性质证明.类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的MSP问题同样具有重要意义,并进一步推动原问题的研究.     

一种多序列比对的局部优化算法

核苷酸序列簇和氨基酸序列簇的比对是分子生物学研究的一种基本工具。多序列比对问题是NP完全问题,任何研究快而完全算法的努力都将面临极大的困难。该文提出了一种多序列比对的局部优化算法,并对基因库中的序列做了测试。     

改进的蚂蚁算法在矩形优化排料中的应用

矩形件优化排料问题是一类具有NP完全难度的组合优化问题.将改进的蚂蚁算法应用到矩形件优化排料问题求解中,优化试验结果表明可获得比基本蚂蚁算法更好的效果,为矩形件优化排料这类NP完全问题提供了新的思路和方法.     

一个具有平均复杂性的SAT问题

最坏复杂性到平均复杂性的归约已被研究很多年。很多NP困难问题是最坏复杂性的。distNP类是平均复杂性的NP类,且有完全问题。LIVEN N证明了所有自然的NP完全问题都有平均复杂性的形式,但是他给出的概率分布是不自然的。在格问题方面,AJTAI和REGEV O分别提出了平均复杂性的困难问题,即短整数解问题(Short Integer Solution,SIS)和带错误学习问题(Learning With Errors,LWE)。给出一个可以归约到判定对于一个NP完全问题是否存在多项式时间算法,对值为1的实例给出一个见证,并且对值为0的实例给出一个归结辩驳的具有平均复杂性的SAT问题。本文方法是将求解NP完全问题的多项式时间算法的存在性转化成SAT问题的一组实例。同时也给出了这个问题的一些变形问题。     

九位不同数字乘法等式的优化算法

对“九位不同数字构成乘法等式”的问题进行研究分析,深入探讨其解决方案,根据NP 问题穷举算法设计的 常规思路,设计了一种更加优化的穷举算法,实验证明该算法是正确高效的。     

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

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

基于模拟退火算法的实体化视图动态选择方法

实体化视图选择问题是NP完全问题,我们通过研究和实验,提出了一种将模拟退火算法应用到实体化视图的动态选择中的方法。在定义了算法的状态、初始状态、目标函数及转换规则之后,深入讨论了模拟退火算法的参数选择对算法解的影响。最后的实验结果表明,模拟退火算法完全可以应用到实体化视图的动态选择中。     

A BDD SAT solver for satisfiability testing: An industrial case study

The satisfiability problem (SAT) is a fundamental problem in mathematical logic, constraint satisfaction, VLSI engineering, and computing theory. Methods to solve the satisfiability problem play an important role in the development of computing theory and systems. In this paper, we give a BDD (Binary Decision Diagrams) SAT solver for practical asynchronous circuit design. The BDD SAT solver consists of a structural SAT formula preprocessor and a complete, incremental SAT algorithm that is able to find an optimal solution. The preprocessor compresses a large size SAT formula representing the circuit into a number of smaller SAT formulas. This avoids the problem of solving very large SAT formulas. Each small size SAT formula is solved by the BDD SAT algorithm efficiently. Eventually, the results of these subproblems are integrated together that contribute to the solution of the original problem. According to recent industrial assessments, this BDD SAT solver provides solutions to the practical, industrial asynchronous circuit design problems.This research is supported in part by the 1993 ACM/IEEE Design Automation Award, by the Alberta Microelectronics Graduate Scholarship, by the NSERC research grant OGP0046423, and was supported in part by the NSERC strategic grant MEF0045793.Presently, Jun Gu is on leave with the Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong.     

求解SAT问题的改进粒子群优化算法

利用限制哆公式的相关理论将可满足性问题（SAT）等价转换为定义在{0,1}^n上的多项式函数优化问题,并将二进制粒子群优化算法（BPSO）与局部爬山搜索策略相结合,给出了一种求解SAT问题的新算法：基于局部爬山搜索的改进二进制粒子群优化算法（简称IBPSO）．数值实验表明,对于随机产生的3-SAT问题测试实例,该算法的计算结果均优于著名的WalkSAT算法和SATI．3算法．     

求解SAT问题的拟人退火算法

该文利用一个简单的变换，将可满足性（SAT）问题转换为一个求相应目标函数最小值的优化问题，提出了一种用于跳出局部陷阱的拟人策略，基于模拟退火算法和拟人策略，为SAT问题的高效近注解得出了拟人退火算法（PA），该方法不仅具有模拟退火算法的全局收敛性质，而且具有一定的并行性，继承性。数值实验表明，对于本文随机产生的测试问题例，采用拟人策略的模拟退火算法的结果优于局部搜索算法，模拟退火算法以及近来国际上流行的WALKSAT算法，因此拟人退火算法是可行的和有效的。     

基于演化算法的SAT问题求解

SAT问题即布尔可满足性问题是逻辑学的一个基本问题,也是计算机科学和人工智能研究的核心问题。寻找求解SAT问题的快速算法不仅在理论研究上而且在许多应用领域都具有极其重要的意义。本文讨论了基于演化算法的SAT问题求解方法。     

NP Problem in Quantum Algorithm

In complexity theory, a famous unsolved problem is whether NP is equal to P or not. In this paper, we discuss this aspect in SAT (satisfiability) problem, and it is shown that SAT can be solved in polynomial time by means of a quantum algorithm if the superposition of two orthogonal vectors |0> and |1> prepared is detected physically.     

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

二元可满足性问题是一个多项式可解的问题．本文首先证明了该问题有解的充要条件，然后给出了判定该问题的一个新的多项式算法．如果判定某个表达式是可满足的话，那么求解算法不需要任何回溯就能准确地给出它的每个解．本文试图通过对二元可满足性的研究为研究其它问题提供一点启示．     

基于粗糙集和SAT算法的属性约简

粗糙集理论是80年代初由波兰数学家Z.Pawlak首先提出的一个分析数据的数学理论。该理论近几年来日益受到各领域的广泛关注,并已在机器学习、模式识别、决策分析、过程控制、数据库知识发现等广泛领域得到成功应用。论文提出了一种求最小约简的基于命题可满足性(简称SAT)算法的算法,提出一个解决SAT问题的分割和结合的算法。实验结果表明,论文所提算法在高度准确分类的基础上,所得约简中大大减少了规则的数目。     

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

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

基于函数变换的求解SAT问题的新算法

提出了一种基于函数变换的求解SAT问题的新算法,这个新算法利用SAT问题自身的特点将判定问题转化为连续函数的求极值问题。随机选取一组初始值,利用最速下降法求解变换后的连续函数在每个初始值邻域内所能达到的局部极值,如果这个局部极值为0,则该SAT问题就是可满足的。实验结果表明：与现有的求解SAT问题的算法相比,基于函数变换的求解算法在求解速度、成功率和求解问题的规模等方面都有明显的提高。     

基于不完全算法的并行FPGA SAT求解器

可满足性问题是计算机理论与应用的核心问题。在FPGA上提出了一个基于不完全算法的并行求解器pprobSAT+。使用多线程的策略来减少相关组件的等待时间,提高了求解器效率。此外,不同线程采用共用地址和子句信息的数据存储结构,以减少片上存储器的资源开销。当所有数据均存储在FPGA的片上存储器时,pprobSAT+求解器可以达到最佳性能。实验结果表明,相比于单线程的求解器,所提出的pprobSAT+求解器可获得超过2倍的加速比。