#CSP的相变及近似算法研究

论文摘要

近年来，相变现象已成为人工智能领域的一个研究热点。对NP完全问题相变的研究可以帮助我们理解问题困难的本质，从而提出更有效的求解算法。相变现象指的是随着某个参数的变化，问题的属性出现突变的情况。比如，对于SAT问题，随着r（子句数/变量数）的增大，问题实例的可满足性发生从几乎都可满足到几乎都不可满足的相变现象。目前有很多关于SAT问题相变的研究，但是除了k=2（k为子句的长度）相变点是确定的，当k>2时，随机可满足问题的相变点都是不确定的，只能给出其上下界。CSP问题是SAT问题的一种泛化形式，目前也有许多从实验和理论两方面介绍关于CSP问题相变的研究。在这些工作中，（Xu and Li2000）是少数证明CSP问题有相变且相变点确定的工作。他们提出了一种新的模型，RB模型。RB模型是B模型的一种变形，但是却有一些特殊的性质。首先，证明了用RB模型生成的CSP问题存在相变现象，且相变点是确定的。其次，无论实验角度还是理论的角度都证明了RB模型可以生成困难的实例（Xu et al2007）。相变现象不仅发生在NP-hard和NP-complete问题中，也出现在更困难的问题中，如QSAT和规划，组合问题的模型计数也成为近年来的一个研究热点。最近研究表明，SAT问题和CSP模型计数的复杂度相当于一致图规划问题和一些概率问题的求解，即为#P完全的。Bailey等人首次证明了SAT的模型计数问题存在相变现象。本文将其扩展为求解CSP模型计数的相变现象，即#CSP的决策问题是存在相变的，#CSP（dn/t）：给定一个CSP实例，是否存在至少dn/t个解。我们证明对于RB模型生成的CSP实例，其相变现象是确切存在的，且相变点也是确定的。对于组合问题的模型计数问题，另一个研究方向为设计算法从而快速求解出问题模型的个数。1999年，Birnbaum等人设计出第一个求解#SAT问题的确定算法CDP，这是求解SAT可满足性算法DP的扩展。随后出现了如组件缓存和子句学习等方法来提高求解#SAT问题的求解效率。由于算法的时间和空间代价一般是随着问题规模的增大而呈指数级的增长，近似算法应运而生，如Approx-count, Sample-count和Sample-Minisat等。对于#CSP问题，Gomes等人在2007通过加入XOR约束的方法近似问题的模型数。本文提出了一个近似CSP问题模型数的新方法，使用我们提出的方法不仅可以高效的求解问题，而且问题的规模越大，算法的精度越高。

论文目录

• 摘要
• Abstract
• 目录
• 引言
• 第一章 #SAT 问题
• 1.1 SAT 问题的概述
• 1.1.1 SAT 问题的定义
• 1.1.2 SAT 问题目前的发展
• 1.1.3 SAT 相变的研究进展
• 1.2 #SAT 问题的相变
• 1.2.1 #SAT 问题的定义
• 1.2.2 #SAT 问题的相变
• 第二章 #CSP 问题的相变现象
• 2.1 CSP 的介绍
• 2.1.1 CSP 的定义
• 2.1.2 CSP 的相变
• 2.1.3 RB 模型
• 2.2 #CSP 的概述
• 2.2.1 #CSP 的定义
• 2.2.2 #CSP 相变
• 2.2.3 定理证明
• 2.2.4 实验
• 第三章 近似求解#CSP
• 3.1 #SAT 近似求解的发展
• 3.1.1 完备算法
• 3.1.2 不完备算法
• 3.2 #CSP 求解
• 3.2.1 精确算法
• 3.2.2 近似求解
• 3.2.3 定理
• 3.2.4 实验
• 结论
• 总结与展望
• 参考文献
• 后记
• 在学期间公开发表论文