【可满足性问题SAT的快速算法的研究】邹波涛.pdf

分类号学校代码:10561 UDC 密级学号:97280 华南理工大学学位论文可满足性问题(SAT)的快速算法的研究邹波涛指导老师:陈光中教授、郝志峰教授应用数学系申请学位级别:硕士专业名称:应用数学论文提交日期:2000 论文答辩日期:2000.

华南理工大学理学硕士学位论文 4如何变换4目标函数4物理意义4跳出策略4算法实现 4实验结果4本章小结第五章权迭代模型5概述5模型理论,符号定义5模糊逻辑 5文字的加权与迭代计算,5计算模型5随机游走的跳出策略 5算法实现5实验结果5本章小结第六章有序搜索的算法模型6DP算法.

华南理工大学理学硕士学位论文摘要研究合取范式可满足性的SAT问题是一个著名的NP完全问题,在人工智能、计算机科学及工程领域中有着中心课题的重要地位,它作为一种基础模型应用在解决各种实际问题中。由于其NP问题的性质决定了它没有通用的多项式时间复杂度的算法。本文基于“实验算法学”的思想,按照平均性态而不是最坏情况性态的原则,对SAT的快速算法进行了探讨和设计,主要分为三部分的研究.SAT问题的变换求解方法的搜索策略是将SAT问题空间从离散空间变换到实域空间,建立布尔变元与实变元,布尔函数与实函数的对应关系,把一个SAT 问题由离散的约束满足问题转化为连续的无约束优化问题。