平衡正则（k，2r）-CNF公式结构信息及相变性质

发布时间：2020-03-21 09:50

【摘要】：布尔可满足性问题是理论计算机科学中的核心问题,人们一直致力于寻找CNF公式实例难解的本质,通过限定CNF公式的结构,如子句长度、布尔变元出现次数等,并以此为基础,分析CNF公式的结构信息,设计高效的求解算法。本文研究的平衡正则(k,2r)-CNF公式是一类具有规则结构的CNF公式,通过限定每个子句的长度为k,每个布尔变元的正出现次数和负出现次数都为r,其实例求解难度比一般的k-CNF公式实例求解难度大。本文从实例生成模型、结构信息、求解算法、相变性质等方面对平衡正则(k,2r)-CNF公式进行研究,主要研究成果如下:(1)为了便于分析平衡正则(k,2r)-CNF公式的结构信息及相变性质,构建了一个生成平衡正则(k,2r)-CNF公式实例的随机模型—BR(n,k,2r)模型。该模型可以有效地生成不重复的平衡正则(k,2r)-CNF公式子句。(2)通过将平衡正则(k,2r)-CNF公式分别表示为变元交互图和因子图,研究了平衡正则(k,2r)-CNF公式的结构信息。实验发现:在变元交互图中,顶点的度与公式的子句变元比正相关;在因子图中,子句与变元呈现交错分布。(3)基于平衡正则(k,2r)-CNF公式特殊的结构信息,改进了随机局部搜索(Stochastic Local Search,SLS)算法的初始赋值方式来求解该类正则公式。实验结果表明:改进后的SLS算法比原算法能更有效地求解平衡正则(k,2r)-CNF公式。(4)平衡正则(k,2r)-CNF公式实例随着子句变元比的增大,会出现可满足性相变现象。通过理论分析,给出了平衡正则(k,2r)-CNF公式可满足性相变阈值点的一个上界为2~kln 2-kln 2/2,一个下界为2~kln 2-kln 2/2-2ln 2.
【图文】：

示意图,变元,子句,难度

元数 n 的比值 α = m /n，通常称之为子句变元比，，它是 k-CNF 公式重要的结构参数，因为其值会影响到k-CNF公式的可满足性及判定说，随着α 的不断增大，存在某个临界值点sα 。当sα < α时，几乎实例都可满足，并称之为高概率可满足；而当sα > α时，几乎全部的不可满足，并称之为高概率不可满足。这种现象被称为随机 k-SAT sα 称为相变阈值点，以 ( )sα k来表示对 k 不同取值的相变阈值点。[47,48]表明随机 2-SAT 的相变阈值点 ( 2 )1sα = ，随机 3-SAT 的相变阈)的值约为 4.267[49]。R. Monasson 与 R. Zecchina 等人[51]于 1999 年发ture》上的文章指出，求解随机 k-SAT 问题在计算复杂性上的分布会殊的“Easy-Hard-Easy”模式，即当子句变元比达到临界值时，k-S满足突变为不可满足，而实例的求解难度则从易于求解变得难于求得易于求解。图 2.1 给出了随机 3-SAT 问题中子句变元比与求解难率的关系示意图。

交互图,二分图,变元,子句

G 称为二分图，记作 ( )1 2G = V , V ,E，E 为 G 的边集合。式的因子图实则是子句变元交互图，此交互图是一个二是以布尔变元集 X 为布尔变元顶点，而另一侧是以子句尔变元出现在一个子句中，表示有一条边连接此变元顶中，其顶点 v 的度（Degree）是指与顶点 v 相关联的边数中每个顶点的度是某一固定整数 k，则称该图是 k-正则图NF 公式的因子图则是一个双正则二分图，在子句顶点为 k；在布尔变元顶点的一侧，每个顶点的度都为 2r。对连接规则：当布尔变元以正文字出现，则以实边相连；当，则以虚边相连。图 2.2 展现了平衡正则( 3,4 )-CNF公式2 3 4 C C∧ ∧ 的因子图，其中， ( )1 1 2 3C = x ∨ x ∨ x， 2 C= ( )1 2 3 x ∨ x ∨ x， ( )4 1 2 3C= x ∨ x ∨ x。CCCC
【学位授予单位】：贵州大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP301.6

【参考文献】