第一章 绪论
1.2 国内外研究现状
CSP 问题在许多学科研究领域中普遍存在[4]。特别是在人工智能领域中绝大多数问题都可以规约为约束性可满足性问题。CSP 的一般形式为指定若干个变元，变元存在若干个不同的赋值指派，而一些约束关系控制着变元的赋值，CSP 问题的最终目的是判断能否找到一组赋值指派满足上述约束关系。
SAT 问题是一类特殊的 CSP 问题，作为第一个被证明的 NP 完全问题，已知的任何类型的算法都无法在多项式时间内对其求得精确解，然而，在各个科研领域以及现实世界中，SAT 问题却又普遍存在。比如在知识表示、并发控制、社区发现和数据挖掘等领域中，许多带有一致性检验、组合优化等问题都可以被规约为 SAT 问题。状态空间搜索是求解 SAT 问题中最先被提出的启发式求解方法，虽然启发式搜索技术能显著提高搜索效率，但是由于规划问题的状态空间是指数级别，因此这样的方法在实践中同样具有很大难度，并且启发式知识往往和相关课题有密切的关系，它的构建方法通常根据问题的不同而有所差异。另一类方法则是基于规划空间搜索的层次，该方法首先对问题按照某种规则进行拆分细化，从而采用“自项向下，逐步求精”思想进行求解。通过拆分不仅可以将整个问题分成若干个子问题进行分析研究，而且对于每一个子问题可以设计针对性的求解策略。该方法需要设计一个完整的求解策略，根据需求不断完善约束和调整参数，直到消除所有对结果不构成影响的因子，再构造出一个可行的算法进行求解，但由于对变元约束条件的构造比较困难，因此求解效率不高。
由于工业应用领域中，SAT 问题的规模越来越大。因此更适用于大规模 SAT 问题随机实例的不完备算法目前吸引了众多研究者的广泛关注。在最近几年，研究者们关于该问题的研究重点是设计更为高效的 SAT 实例产生模型和对现有模型进行研究，以及设计可行性更高，结果更为准确的不完备求解算法。在关于 SAT 实例产生模型研究方面，由于 3-SAT 问题的特殊性，因此学者研究最为广泛和深入的是 3-SAT 实例产生模型，3-SAT 实例产生模型中，α是子句和变元规模的比值，相关研究表明α取值与 SAT 问题随机实例的可满足性和实例的判定难度密切相关[5]。
目录
第三章 信息传播算法分析
3.1 多维结构熵在 WP 算法性能分析中的应用
WP算法虽然在求解SAT问题中往往具有优良的性能表现，但该算法有时会失效，往往表现为不收敛，尤其当因子图不是简单的树形结构，而是其中包含多个环路的一般图状结构时，则该算法的收敛性无法保证，但是对于这样的现象，至今缺少系统地研究给予理论解释。因此本节基于WP算法的信息迭代策略，利用高维结构熵度量因子图的结构复杂性，从而分析研究WP算法在含有多环路的一般结构因子图上的收敛性表现。
3.1.1 因子图转换技术
在概率论及其应用中，最常见的概率图就是贝叶斯网络(Bayesian Network)和马尔可夫随机场(Markov Random Fields)，因子图作为概率图中的一种特殊图结构，在贝叶斯推理中得到了广泛应用。在概率图中，求某个变量的边缘概率分布是最为常见的问题，并且，求解过程往往借助某个计算模型或者是一种具体算法，一般无法对因子图本身的结构直接进行计算和分析。因此，为了计算命题公式的结构熵，需要把命题公式的因子图模型转换为带权无向图模型，利用相应的带权无向图模型建立结构熵计算模型，从而分析因子图的结构。由于因子图利用了两类节点(子句节点和变量节点)映射CNF公式中的子句和变量，并用虚边和实边表示节点之间的关系，子句 *含正文字 *时，子句节点和对应变量节点的连线为虚线，子句 *含负文字¬ *时，子句节点和对应变量节点的连线为实线，这样的结构可以最直观表达因子图和对应公式的映射关系以及便于描述WP算法的运算过程。
图3-1 带权无向图
第五章 总结与展望
5.2 展望
由于课题的研究内容比较复杂，涉及的相关领域知识比较多，因此本课题的研究范围和研究深度仍然有很大的提升空间，本课题接下来的任务也十分艰巨:
（1）信息传播算法的研究尚不完善，不论是用于求解 SAT 问题的相关算法还是人工智能领域中的信息传播算法，都有明显的缺陷，因此，设计一种限制条件更少、求解效率高、速度更快的信息传播算法用来突破约束可满足性问题的瓶颈具有十分重要的意义。
（2）信息传播算法是一类原理十分复杂的算法，目前对 SP 算法的相关研究较少，但是由于SP 算法往往在变元规模较小的实例中的求解效率相较其他信息传播算法更高，因此，更加深入的研究 SP 算法的原理以及对其作出改进可以填补该类算法研究中的空白.
（3）二维结构熵和高维结构熵可以用于度量复杂网络的结构复杂性，本文尝试利用他们去度量因子图可以获得不错效果，但是针对因子图设计一种更为准确的度量方式并且建立度量模型可以使得到的信息传播算法收敛性条件更为精准。
（4）本文所提的 WPLPA 算法可以有效划分因子图社区结构，但是该算法在理论上具有更为广泛的应用领域，下一步将对该算法进行优化。保留其本身的优良性质，将算法应用于真实的社交网络社区发现中。
参考文献（略）
