基于因子图求解(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可满足。

LPA-SKFST半监督特征提取方法

针对传统LDA类半监督特征提取方法的解矢量非正交、解空间不稳定和非线性处理能力不足等问题,提出LPA-SKFST方法。该方法的前置级LPA通过标签传播提高标记样本容量,后置级SKFST(半监督核最佳鉴别矢量集)采用双向正则方法对KFST引入全局结构保持正则和Tikhonov正则,并以成对空间求解方法求取Fisher分母矩阵奇异和非奇异时的统一形式解。在circle、iris、wine和自有珍珠光谱集的分类实验中,PCA、LDA、SLDA和SDG组的准确率随样本集、标记样本占比和标签可靠性变化而波动,LPA-SKFST组则稳定保持在85%以上。该结果证明,LPA-SKFST能克服标记样本占比和标记可靠性不足局限,在实际集和线性不可分人工集上取得一致、稳定的优秀表现。

基于图分解的(3,4)-CNF公式的可满足性

对于规则的(3,4)-CNF公式F,公式F对应的因子图GF恰好是一个(3,4)-双向正则二部图。利用正则二部图的有关性质,证明了对于任意的(3,4)-CNF公式F,若其对应的因子图GF能够被划分为两个(3,2)-双向正则二部图,则F是可满足的。