中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 学位论文
学科主题: 计算机科学技术基础学科::计算机科学技术基础学科其他学科
题名:
可满足性问题研究
作者: 贾祥雪
答辩日期: 2010-05-31
导师: 张健
授予单位: 中国科学院研究生院
授予地点: 北京
学位: 博士
关键词: SAT,同构,剪枝,Local Lemma,DASH
摘要: 数理逻辑是计算机科学的基础,而逻辑公式的可满足性问题是计算机科学和人工智能领域中的一个著名而又重要的问题。它在计算机科学和人工智能研究中有广泛的应用。本文将重点介绍实际可用的判定算法及其相关技术。 本文的研究分两大方向,分别是命题逻辑的可满足性问题研究和一阶逻辑的可满足性问题研究。命题逻辑的可满足性问题(Satisfiability Problem)是一个历史悠久的问题,一般简称为 SAT问题。SAT 问题的求解算法有两大类,分别是确定性算法和非确定性算法。本文只研究确定性算法的相关内容,尤其是如何进行剪枝。我们充分调研了SAT求解算法和求解工具的相关知识,在此基础上,提出了local Lemma 这个剪枝技术,该技术可以更加充分地挖掘剪枝信息,达到进行更多剪枝的目的。 在一阶逻辑的可满足性问题研究方面,本文采取直接搜索可行的一阶逻辑模型的方法研究有限论域上的一阶逻辑的可满足性问题。该方法本质上就是深度优先的回溯搜索。因此,我们的研究重点就是如何找到问题的更高效的一阶逻辑的表示以及如何采用启发式的方式进行剪枝。在这个问题上,我的主要工作有两个:一个是模型搜索中适用于谓词的同构消去技术,包括Row by Row策略和Ramsey Number 策略两个技术;另一个是 DASH(Decision Assignment Scheme Heuristic),用来在生成有限模型的时候边搜索边消除同构子空间。DASH 能用近乎零代价保证输出的模型都是互不同构的。这两个技术都是基于有限论域中的元素的固有对称性,换言之,就是需要有限论域中的元素是两两可交换的。 在已有的成果的基础上,我们又尝试使用它们去求解一些数学中的实际问题,如拟群拉丁方,有限射影平面,正交拉丁方(组)等。我们给出了在这几个方面的一些尝试和初步结果,包括一个重要的定理和若干效率提高了几个数量级的改进。 值得一提的是,和马菲菲共同提出的横截矩阵(Transversal Matrix)概念是一个新颖的成果,使得正交拉丁方的表示和求解取得了明显的改进。在这个概念的基础上,进一步给出了几个定理,进行了理论上的拓展。实验数据表明,我们的求解途径和技术能有效解决拉丁方相关的问题。
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/2302
Appears in Collections:计算机科学国家重点实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
博士学位论文_贾祥雪.pdf(1710KB)----限制开放 联系获取全文

Recommended Citation:
贾祥雪. 可满足性问题研究[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