Institutional Repository
| SAT和DSOLS问题的研究 | |
| 卢闰明 | |
| Major | 计算机软件与理论 |
| Supervisor | 张健 |
| 2010-05-31 | |
| Degree Grantor | 中国科学院研究生院 |
| Degree Level | 硕士 |
| Place of Degree Grantor | 北京 |
| Keyword | Sat Dsols 约束可满足性问题 |
| English Abstract | 约束可满足性问题（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)不存在。 |
| Subject | 人工智能其他学科 |
| Language | 中文 |
| Content Type | 学位论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/2846 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | 卢闰明. SAT和DSOLS问题的研究[D]. 北京. 中国科学院研究生院,2010. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| template.pdf（843KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment