SAT和DSOLS问题的研究
文献类型:学位论文
作者 | 卢闰明 |
学位类别 | 硕士 |
答辩日期 | 2010-05-31 |
授予单位 | 中国科学院研究生院 |
授予地点 | 北京 |
导师 | 张健 |
关键词 | SAT DSOLS 约束可满足性问题 |
学位专业 | 计算机软件与理论 |
中文摘要 | 约束可满足性问题(Constraint Satisfaction Problem,CSP)是在人工智能领域被广泛研究的一类问题。对CSP问题的研究有两种重要的思路:一种思路是用统一的模型来表示CSP,然后用针对这个统一模型的通用工具进行求解;另外一种思路是针对不同的CSP问题开发专门工具,设计不同的算法和数据结构来求解。 本文研究了两个CSP问题:SAT(SATisfiability problem)和DSOLS(DoublySelf-Orthogonal Latin Squares)。CSP可以方便的转换为SAT来求解,因此对SAT的研究对很多问题具有重大意义。本文介绍了当前流行的SAT solver的一些技术,也提出一种新的搜索空间裁剪策略Local Lemma。DSOLS是一种具有特定性质的拉丁方,本文对它的研究不仅仅因为它的应用意义。更重要的是它作为一个特定的CSP问题,可以用来比较通用工具和专门工具的优劣。本文尝试了把DSOLS转化为SAT求解,也试过用一般CSP的思路来求解,最后提出了一种针对性的高效算法并开发了一个专门工具DSOLver,用这个工具证明了一个开放问题:DSOLS(10)不存在。 |
学科主题 | 人工智能其他学科 |
语种 | 中文 |
公开日期 | 2010-07-09 |
源URL | [http://124.16.136.157/handle/311060/2846] ![]() |
专题 | 软件研究所_计算机科学国家重点实验室 _学位论文 |
推荐引用方式 GB/T 7714 | 卢闰明. SAT和DSOLS问题的研究[D]. 北京. 中国科学院研究生院. 2010. |
入库方式: OAI收割
来源:软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。