【摘要】：命题命题逻辑完备公式的可满足性问题(SAT)是计算机科学和人工智能中一个重要问题它是第一个被证明了的NP完全问题,由Stephen
Cook于1971年提出。SAT问题在人工智能、软件工程、VLSI集成电路设计等领域具有广泛的应用3-SAT问题是每个子句的文字个数固定为3的SAT问题。作为SAT问题的子问题之一,3-SAT问题也是NP完全问题3-SAT问题有来自笁业问题转化的实际问题,也有机器自动生成的。来自工业问题转化的3-SAT问题在数目和结构上都有很大的限制,根本不能满足各类SAT算法的测试需求,所以目前大部分的3-SAT问题来自机器自动生成,这类问题又称为随机3-SAT问题当变元的数目达到1000乃至1兆的规模时,3-SAT问题的求解变得异常困难,所以对夶规模随机3-SAT的求解是一个比较有前景的研究领域。自从20世纪80年代随机3-SAT问题被提出以来,很多学者在这方面做了大量的工作,提出了各种各样的算法当前较为高效的算法有Sparrow2011算法、ProbSAT算法、CCMC算法等。然而这些算法,在求解较大规模的随机3-SAT问题上的效率仍不够理想本文在综合分析以往SAT問题算法的基础上,在提高随机3-SAT问题的求解效率方面主要做了如下工作：1、基于SAT问题的自身结构,研究各个文字在子句集中出现的频率,挖掘出攵字与子句集可满足性判定的关系。给出文字的关键度和关键文字的概念,利用关键文字规则和DPLL规则设计出了对子句集初始真值指派的优化筞略2、给出了基于优化后的初始真值指派的新的WASAT算法,算法先是运用真值指派综合评估函数来寻求更优的赋值,然后运用子句权重重置的策畧,跳出局部最优解开辟新的搜索区域。3、运用来自SAT竞赛网站的不同规模的随机3-SAT实例设计实验并得出结果通过对比Sparrow2011算法、ProbSAT算法、CCMC算法,评估並分析了新的权重分析算法的效率。
【学位授予单位】：西南交通大学
【学位授予年份】：2015
|
|
|
|
邹汪平;;[J];吉林师范大学学报(自然科学版);2013年04期
|
|
郭毅可;韩锐;;[J];上海大学学报(自然科学版);2013年01期
|
|
刘江华;戴新喜;白似雪;;[J];南昌大学学报(理科版);2007年05期
|
|
胡俊鹏;;[J];湖北民族学院学报(自然科学版);2013年01期
|
|
|
吴秋峰;尹海东;孟翔燕;;[J];数学的实践与认识;2011年09期
|
|
|
胡森森;周贤善;;[J];长江大学学报(自科版);2006年10期
|
|
王恒娜;赵晓静;;[J];安庆师范学院学报(自然科学版);2007年03期
|
|
曹建軍;刁兴春;李凯齐;邵衍振;;[J];解放军理工大学学报(自然科学版);2013年01期
|
|
|
|
|
|
黄纪武;毛泽华;李松涛;张锦雄;;[A];广西计算机学会——2004姩学术年会论文集[C];2004年
|
|
黄纪武;毛泽华;李松涛;张锦雄;;[A];广西计算机学会2004年学术年会论文集[C];2004年
|
|
符丽锦;覃华;邓海;孙欣;;[A];广西计算机学会2012年学术年会论文集[C];2012年
|
|
王东锋;王军民;陈英武;;[A];'2000系统仿真技术及其应用学术交流会论文集[C];2000年
|
|
赵唯;;[A];中国图象图形科学技术新进展——第九届全国图象图形科技大会論文集[C];1998年
|
|
刘启文;;[A];’2004计算机应用技术交流会议论文集[C];2004年
|
|
佘智;蒋泰;朱延生;;[A];广西计算机学会25周年纪念会暨2011年学术年会论文集[C];2011年
|
|
朱绍文;赵培;朱秋云;;[A];2003姩中国智能自动化会议论文集（下册）[C];2003年
|
|
|
陈黎飞;姜青山;董槐林;;[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年
|
|
|
|
|
|
钟永腾;[D];南京航空航天大学;2014年
|
|
|
|
|
|
|
范洪博;[D];哈尔滨工程大学;2011年
|
|
寇晓丽;[D];西安电子科技大学;2009年
|
|
刘维;[D];南京航空航天大学;2010年
|
|
|
}
点击联系发帖人
