基于膨胀图的随机算法求解SAT问题

论文摘要

膨胀图是有很好连通性的稀疏图。它的每一个不太大的结点集都有一个相对更大的邻接结点集,因此,要想使图不连通,需要切断许多边。由于膨胀图的这一特性,使得它在理论与实践中发挥着极其重要的作用,横跨数学、通信和计算机等多个领域,如算法设计、密码学、纠错码、伪随机信号发生器、排序网络及健壮的计算机网络等方面。在理论计算机科学中,由于膨胀图在某些方面与随机图类似,尤其是能够降低随机算法对随机位的依赖程度,因此正越来越引起科学家们的关注,被用于证明计算复杂性理论的许多结论。我们知道,命题公式的可满足性问题是理论计算机科学和人工智能中的著名问题,判断命题公式可满足性的一个直接办法是穷举法。这种办法从理论上讲是可行的,但计算时间动辄达到天文数字。而其它算法,如DPLL算法、局部随机搜索算法等也各有其优缺点。因此,高效实用的SAT算法设计与分析一直是计算机科学界的研究热点。本文对膨胀图的理论进行了较为全面的分析,并以膨胀图为基础,提出了一种新的SAT算法。首先,从组合学角度介绍了膨胀图的基本概念和性质;其次,从代数学角度对膨胀图族的构造进行研究,介绍了正则图的三种积运算:矩阵积、直积、替换积,并利用三种积各自的特点进行膨胀图族的构造;再次,从概率论角度对膨胀图的随机步进行深入研究,详细介绍了膨胀混合引理及随机步概率估计,进而将膨胀图应用于随机算法的设计;最后,对可满足性问题、随机算法、SAT算法的分类进行介绍,并将膨胀图与已有的SAT算法相结合,利用膨胀图来诱导SAT算法搜索的随机步,最终提出了基于膨胀图的SAT随机算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 膨胀图的研究历史及现状
• 1.3 本文的主要内容
• 第二章 膨胀图理论的基本概念及方法
• 2.1 膨胀图概述
• 2.1.1 膨胀图的有关概念
• 2.1.2 膨胀图的性质
• 2.2 正则膨胀图
• 2.2.1 正则膨胀图的概念
• 2.2.2 膨胀图族的存在性
• 2.3 膨胀图的分类
• 2.4 膨胀图的扩张
• 2.5 膨胀图的应用举例
• 第三章 膨胀图族的构造
• 3.1 膨胀图的代数定义
• 3.2 正则图的表示方法
• 3.3 正则图的三种积运算
• 3.3.1 矩阵积
• 3.3.2 直积
• 3.3.3 替换积
• 3.4 基于三种积的膨胀图族的构造
• 第四章 膨胀图的随机步
• 4.1 基本知识
• 4.2 混合引理与随机步概率上界估计
• 4.3 随机步概率估计
• 4.4 膨胀图上随机步在算法设计中的应用
• 第五章 可满足性问题及其求解算法
• 5.1 基本概念
• 5.1.1 约束满足问题（CSP）
• 5.1.2 可满足性问题（SAT）
• 5.2 算法简介
• 5.2.1 随机算法及其分类
• 5.2.2 SAT算法分类
• 5.3 求解SAT问题的随机算法
• 5.4 基于膨胀图求解SAT问题的随机算法
• 致谢
• 主要参考文献
• 附录