警示传播算法收敛的充分条件

信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播（warning propagation,简称WP）算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明：当子句与变元的比值α<1.8时,该判定条件有效.     

正则(3,4)-CNF公式的社区结构

通过构造适当的极小不可满足公式以实现在多项式时间内将3-CNF公式归约转换为一个正则(3,4)-CNF公式,转换后的公式与原公式具有相同的可满足性,同时公式的结构也发生相应的变化。图的社区结构反映了图的模块特性,文中将CNF公式转化为相应的图,研究公式图的模块特性与公式某些性质之间的关系。将归约前后的两类公式转换为相应的图并研究其模块特性,发现转换后得到的正则(3,4)-CNF公式具有较高的模块度。此外,在使用DPLL(Davis Putnam Logemann Loveland)算法求解CNF公式的过程中,发生冲突时利用冲突驱动子句学习策略,得到一个学习子句并将其添加到原公式中,使得原公式的模块度降低。研究发现:将DPLL算法与冲突驱动子句学习策略结合应用到正则(3,4)-CNF公式时,其学习子句所包含的绝大部分变元位于不同的社区中。     

取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界

3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则（k,2s）-CNF公式.受严格正则（k,2s）-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则（k,2s）-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机（k,2s）-CNF公式.取定整数5<s<11,模拟实验显示,严格d-正则随机（3,2s）-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机（3,2s）-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法,得到了严格d-正则随机（3,2s）-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.     

用于求解正则(3,4)-SAT实例集的修正警示传播算法

利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高概率收敛,但在任意一个实例上都无法判断公式的可满足性,因此算法求解失效。对于一个归约转换后的正则(3,4)-CNF公式,每一变元出现的正负次数之差具有趋于稳定的结构特征,基于该特征,提出基于变元正负出现次数规则的WP算法来求解归约转换后的正则(3,4)-SAT实例。实验结果表明,修正的WP算法对正则公式的可满足性判定有效,从而可以利用公式的正则性特征进一步研究WP算法的收敛性特征条件。     

PCP定理及其在不可近似问题研究中的应用

PCP定理是近十年来计算复杂性领域内的重要成果之一,介绍了从图灵计算模型到概率可验证明(PCP)计算模型的演变过程、PCP系统的基本理论,以及PCP定理应用于不可近似问题研究的基本原理和方法。     

游戏中寻找路径的改进算法

通过分析A*算法,设计并实现用索引数组和二叉堆表示开放列表的A*改进算法。该算法与用索引数组表示的开放列表相比,可以节省约11%的运行时间。     

有限随机系统的极限性质

有限随机系统状态迁移过程中对系统状态集的压缩,将系统分为两类随机子系统,由此建立该随机系统的商系统。在商系统中,根据不完整子系统概率矩阵的特征,引入弱概率矩阵的定义,并结合弱概率矩阵的极限性质,考察商系统对应的概率矩阵的极限性质。在保留原有随机系统的极限性质的前提下极大地降低了计算复杂度。     

大图中子图的可测性质

对于给定的距离参数。,性质测试算法A需以高概率正确地区分给定的对象具备预定性质II与二远离性质 II。若存在II的测试算法A满足其询问复杂性独立于规模参数n,则称II是可测的。设H是一个图,性质仔了)℃。为 不含井子图的图所构成的集合。在有界度模型中,Goldreich与Ron证明了对任意连通图H,性质仔力℃。是可测 的}s}。在邻接矩阵模型中,证明了对任意图H,不管其连通与否,性质件厂re。是可测的。     

基于因子图求解(3,4=)-CNF公式类下可满足问题

合取范式(CNF)公式F是(3,4=)-CNF公式,如果F中每个子句的长度是3,每个变元出现的次数恰好为4次.与(3,4=)-CNF公式所关联的因子图是一类规则的二部图,即每个子句结点的度为3,每个变元结点的度为4,此类规则图被称为(3,4)-双向正则二部图.对于一个(3,4=)-CNF公式F,如果它关联的因子图GF有P7路径因子,则F可满足.     

基于2D-KPCA的拉普拉斯特征映射人脸识别*

针对拉普拉斯特征映射(LE)只能保持局部近邻信息,对新测试点无法描述的不足,提出一种基于二维核主成分分析的拉普拉斯特征映射算法(2D-KPCA LE)。与核二维主成分分析算法(K2DPCA)不同,该算法首先对训练样本空间进行二维主成分分析（2DPCA）,在保留样本空间结构信息的同时通过去相关性得到低秩的投影特征矩阵;然后用核主成分分析法(KPCA)提取全局非线性特征;由于其核函数需要大量存储空间,再用拉普拉斯特征映射(LE)进行降维。在ORL和FERET人脸数据库中的仿真实验结果表明,基于2D-KPCA的拉普拉斯特征映射算法不但可以有效处理复杂的非线性特征,又可以降低算法复杂度,提高流形学习的识别率。