| 【中文题名】 | 可满足性问题的约束规划算法研究 |
| 【英文题名】 | Constraint Planning Algorithm-Based SAT Problems |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-9-24 |
| 【中关键词】 | SAT问题,约束规划算法,搜索引擎,数学建模,实验分析, |
| 【英关键词】 | SAT problems,Constraint planning algorithm,Search engine,Modeling,Experimental analysis, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>一般性问题>理论、方法>算法理论 |
| 【论文摘要】 |
可满足性问题(简称SAT问题)是NP-hard问题，它是当前运筹学、人工智能和计算机科学的热点领域，解决SAT问题具有突出的理论价值和应用价值。解决SAT问题的传统算法往往要占用很长时间和大量的内存，而最后往往还不能得到满意的结果。为了提高SAT问题解决算法的性能，本文对于SAT问题做了对已有算法的分析研究、约束规划算法分析、约束规划算法的UML建模和约束规划算法来求解SAT问题的实验分析等方面的探讨，主要的内容有：
对SAT问题已有的主要算法及存在的问题进行了研究，总结了提高算法性能和跳出局部陷井所用的策略或机制。对局部搜索算法的实验分析，针对局部搜索算法的灵活性、随机性和参数化等特点，深入探讨了相应的算法实验分析所涉及的算法性能度量、性能比较和参数调优等基本问题。提出了综合人工智能中一致性算法和启发式搜索算法，采用约束推理的方法的约束规划算法。本文通过对约束规划算法事件触发机制的分析和UML的建模，从而提高了搜索效率，提出了解决SAT问题。
结合SAT问题特殊知识，提出了在启发式算法和一致性算法的基础上，采用整数有限域的优化和搜索策略，对非线性约束问题在其内部制作二叉树进行搜索的... |
| 【论文题纲】 |
|
摘要 |
4-6 |
|
ABSTRACT |
6-12 |
|
第一章 绪论 |
12-18 |
|
1.1 研究背景 |
12-14 |
|
1.2 SAT问题的有关定义 |
14 |
|
1.3 SAT问题规划方法研究及存在的问题 |
14-16 |
|
1.4 SAT问题研究方法特点 |
16-17 |
|
1.5 研究课题介绍 |
17-18 |
|
第二章 SAT问题的已有算法研究 |
18-37 |
|
2.1 研究简介 |
18-19 |
|
2.2 DPLL算法 |
19-22 |
|
2.3 局部搜索算法 |
22-26 |
|
2.4 其他算法 |
26-29 |
|
2.5 局部搜索算法的实验分析 |
29-34 |
|
2.6 算法的分析与比较 |
34-37 |
|
第三章 约束规划算法分析 |
37-48 |
|
3.1 基本原理 |
37-38 |
|
3.2 组件构成 |
38-43 |
|
3.3 变量压缩事件分析 |
43-46 |
|
3.4 总结 |
46-48 |
|
第四章 约束规划算法的UML建模 |
48-55 |
|
4.1 UML建模语言介绍 |
48-50 |
|
4.2 约束规划算法的建模过程 |
50-53 |
|
4.3 约束过滤器的可扩展性分析 |
53-54 |
|
4.4 总结 |
54-55 |
|
第五章 约束规划算法的FLYING-TT平台 |
55-64 |
|
5.1 约束过滤器 |
55-59 |
|
5.2 分支策略 |
59-61 |
|
5.3 搜索策略 |
61-63 |
|
5.4 内存分配策略 |
63-64 |
|
第六章 约束规划算法的实际应用分析 |
64-74 |
|
6.1 约束规划模型的建立 |
64-68 |
|
6.2 约束规划算法求解SAT问题 |
68-70 |
|
6.3 实验及分析 |
70-73 |
|
6.4 总结 |
73-74 |
|
第七章 结论 |
74-75 |
|
参考文献 |
75-78 |
|
附录 |
78-79 |
|
致谢 |
79-80 |
|
研究成果及发表的学术论文 |
80-81 |
|
作者简介 |
81-82 |
|
硕士研究生学位论文答辩委员会决议书 |
82-83 |
|
| 【DOI】 | LunWen.ID:2.2008.362137 |
