警示传播算法求解正则（3,4）-SAT问题

发布时间：2022-07-14 09:29

　　利用极小不可满足公式的临界特性,可以将任意一个3-CNF公式多项式时间归约转换为一个正则（3,4）-CNF公式,从而得到一个保留NP完全性的正则（3,4）-SAT问题。对于归约转换后的正则（3,4）-SAT实例集而言,警示传播算法（Warning Propagation,WP）在其上高概率收敛,然而难以有效地返回关于变元的一组真值指派（如果该实例可满足）。因此,在归约转换下的正则（3,4）-SAT问题上,WP算法求解失效。本文围绕该问题,基于归约转换下正则（3,4）-CNF公式的结构特征,提出了WP算法的一种修正策略来专门用于求解归约转换下的正则（3,4）-SAT实例。同时基于WP算法的信息传播机制,引出了WP-可解公式的结构定义,探索了WP算法的收敛性特征条件。主要的研究成果如下:（1）从三个方面比较了归约转换后的正则（3,4）-CNF公式与原3-CNF公式在公式的结构特征上所发生的变化:一是归约转换后的正则（3,4）-CNF公式中变元正负出现次数之差趋于稳定;二是归约转换后的正则（3,4）-CNF公式中每个变元至少被包含在两个圈中;三是一个归约转换后且可满足的正则（3,4）-CNF... 

【文章页数】：55 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景
    1.2 国内外研究现状
    1.3 论文研究的主要内容
    1.4 论文的组织结构
第二章 基础知识
    2.1 可满足性问题
    2.2 因子图
    2.3 警示传播算法
    2.4 本章小结
第三章 归约转换下正则(3,4)-CNF公式的结构特征
    3.1 变换构件
    3.2 3-CNF公式转换为正则(3,4)-CNF公式的变换技术
    3.3 归约转换下正则(3,4)-CNF公式的结构特征
    3.4 本章小结
第四章 求解正则(3,4)-SAT实例集的修正警示传播算法
    4.1 问题描述
    4.2 警示传播算法的改进
    4.3 修正的警示传播算法求解正则(3,4)-SAT问题
    4.4 本章小结
第五章 WP-可解公式上警示传播算法的收敛性
    5.1 WP-可解公式的结构定义
    5.2 生成可满足实例的随机算法
    5.3 WP-可解公式上警示传播算法的收敛性
    5.4 本章小结
第六章 结束语
    6.1 论文主要工作总结
    6.2 论文中存在的不足
    6.3 研究展望
致谢
参考文献
附录
图版



本文编号：3660870