中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 学位论文
学科主题: 人工智能::人工智能其他学科
题名:
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)不存在。
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/2846
Appears in Collections:计算机科学国家重点实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
template.pdf(843KB)----限制开放 联系获取全文

Recommended Citation:
卢闰明. SAT和DSOLS问题的研究[D]. 北京. 中国科学院研究生院. 2010-05-31.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[卢闰明]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[卢闰明]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace